Array Simulation

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:

1. 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.
2. You will be given l, r, m. You have to multiply each value between l & r inclusive by m.
3. You need to set each value to s between l & r inclusive where you will be given l, r & s.
4. 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

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.