You are given an array of N elements. Initially all the indices have a value of 0. You have to do four types of works on this array:
You will be given l, r, a & d. You have to add a in l, a + d in l + 1, a + 2d in l + 2, a + 3d in l + 3, .... , a + (r β l) β π in r.
You will be given l, r, m. You have to multiply each value between l & r inclusive by m.
You need to set each value to s between l & r inclusive where you will be given l, r & s.
You have to answer the summation of all the numbers between l & r inclusive.
Now you have to complete all this tasks.
Input
The first line contains an integer T (T β€ 5) indicating the number of test cases.
Each test case starts with two numbers N & M (1 β€ N, M β€ 100000). N is the number of elements and M is the number of tasks you need to complete.
Next M lines contains one of the following four lines:
1 l r a d β indicating the type 1 task (1 β€ l, r β€ N; 1 β€ a, d β€ 1000000).
2 l r m β indicating the type 2 task (1 β€ m β€ 1000000).
3 l r s β indicating the type 3 task (1 β€ s β€ 1000000).
4 l r β indicating the type 4 task.
Output
For each test case, you have to print βCase X:β on the first line, where X is the case number.
After that for each task of type 4, you need to print a line, summation of all the numbers between π & π inclusive. As the numbers can be very large, you need to answer the sum modulo 100000007.
Sample
Input
Output
1
5 6
1 2 4 1 1
4 1 5
2 1 5 2
4 1 5
3 1 3 3
4 1 5
Case 1:
6
12
15
This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizerβs request.