Range of Data

All submissions for this problem are available.
Alice has N pieces of paper.
These papers are numbered from 1 to N.
She writes down the numbers 1 to N in order (one number on each paper),
i.e. paper i has number i written on it.
Bob messes the numbers on these papers.
He either adds a constant to a number or subtracts a constant from the number.
He performs M such operations.
Each operation is of the form: w x y z where each of them is an integer.
If w = 1, then Alice has to add z to every number on papers x to y (both inclusive).
If w = 2, then Alice has to subtract z from every number on papers x to y (both inclusive).
After doing this, Bob challenges Alice to tell him the range of this data,
where range denotes the count of numbers from the smallest number to the largest (See here for more details).
Your task is to help Alice in finding the range.
Input:
First line of input contains a single integer T, the number of test cases.
Each test case starts with a line containing two space separated integers N and M.
Then follow M lines. Each of these lines is of the form w x y z. Each separated by a single space.
Output:
For each test case output a single line containing the range of the new data set after Bob's modifications.
Constraints:
1 ≤ T ≤ 20 1 ≤ M ≤ 10000 1 ≤ N ≤ 1000000 1 ≤ x ≤ y ≤ N 0 ≤ z ≤ 100000
Example:
Input 1 10 2 2 3 6 4 1 5 9 1 Output: 11
Explanation: Initially the papers are as follows: 1 2 3 4 5 6 7 8 9 10. First operation decreases the numbers on paper number 3,4,5 and 6 by 4. Now, the papers look like: 1 2 1 0 1 2 7 8 9 10. The second operation increases the numbers on papers 5 to 9 by 1. The numbers will now be 1 2 1 0 2 3 8 9 10 10. Thus, the range is 10  (1) = 11.
Author:  vamsi_kavala 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/DRANGE 
Tags  adhoc, aug12, differenceseq, vamsi_kavala 
Date Added:  1072012 
Time Limit:  0.243728 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, 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