Sereja and Commands

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Sereja has an array A consisting of n integers. Initially, all the elements of array are zero.
Sereja writes down m commands on a piece of a paper. The commands are enumerated from 1 to m. These commands can be of the following two types of commands:
 l r (1 ≤ l ≤ r ≤ n) — Increase all elements of the array by one, whose indices belongs to the range [l, r]
 l r (1 ≤ l ≤ r ≤ m) — Execute all the commands whose indices are in the range [l, r]. It's guaranteed that r is strictly less than the enumeration/number of the current command.
Can you please help Sereja in executing all the commands written on this piece of paper.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line contains integers n and m. Next m lines contain Sereja's commands in the format, described in statement: t, l, r, where t  number of type (1 or 2).
Output
For each test case on different lines print an array a, after executing all the commands. The numbers have to be separated by spaces. As the numbers can be quite large, print them modulo 10^{9} + 7.
Constraints
 1 ≤ T ≤ 3
 1 ≤ n, m ≤ 10^{5}
Subtasks
 Subtask #1 (20 points): 1 ≤ n, m ≤ 10
 Subtask #2 (30 points): 1 ≤ n, m ≤ 1000
 Subtask #3 (50 points): original constraints
Example
Input: 3 5 5 1 1 2 1 4 5 2 1 2 2 1 3 2 3 4 1 2 1 1 1 1 1 1 10 10 1 1 10 2 1 1 2 1 2 2 1 3 2 1 4 2 1 5 2 1 6 2 1 7 2 1 8 2 1 9 Output: 7 7 0 7 7 2 512 512 512 512 512 512 512 512 512 512
Explanation:
Example case 1..
After the first command, the resulting array is [1 1 0 0 0], after second [1 1 0 1 1].
On third command, we repeat the 1'st and the 2'nd command, so that resulting array is [2 2 0 2 2].
After fourth command, the array will looks like [4 4 0 4 4].
Last command will apply 3'rd and 4'th commands, which by themselves will apply 1'st, 2'nd, 1'st, 2'nd, 3'rd(1'st, 2'nd), so resulting arrays is [7 7 0 7 7].
Author:  sereja 
Editorial  https://discuss.codechef.com/problems/SEACO 
Tags  easymedium, fenwicktree, sept17, sereja 
Date Added:  28052013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions