Limits 2s, 512 MB

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

InputOutput
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.

Submit

Login to submit.

Statistics

47% Solution Ratio
seyedsszEarliest, Jan '17
nusuBotFastest, 0.3s
JohnCenaLightest, 9.2 MB
failed_coderShortest, 3027B
Toph uses cookies. By continuing you agree to our Cookie Policy.