The Street

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The String street is known as the busiest street in Codeland.
Tourists from all over the world want to visit the street once they are in Codeland.
The Chef owns N souvenir stores across the street (numbered from 1 to N).
At the beginning there is no souvenir in any store, the Chef has some plans to add some new items.
Each the Chef's plan is represented by 4 numbers: u v a b which mean an items with price b
is added to the store u, an items with price a + b is added to the store u + 1 and so on.
More formally, an item with price a * i + b is added to the store u + i for all (0 ≤ i ≤ v  u).
In additional to the cost of the item itself, the tourist must pay some conservation fees as well.
The Codeland regularly defines the new conservation fee. Each fee is represented by 4 numbers: u v a b which means
the tourist buying any item in the store u + i will be charged a fee of i * a + b for all (0 ≤ i ≤ v  u).
In the case that several conservation fees have effect on the same store, the customer needs to pay all of those fees.
At some point of time, a tourist at store i asks you what is the largest amount of money they have to spend for
a souvenir at that store (the amount of money includes the price of one of the souvenirs and all the conservation fees for that store).
Input
 The first line of the input contains two integers N and M represent the number of stores and the number of events
 Each of the next M lines represents an event of three types below in the chronological order.
 The new plan of the Chef: "1 u v a b".
 The new conservation fee: "2 u v a b".
 The query from tourist: "3 i".
Output
For each query from tourist, print in one line the corresponding answer.
If there is no item at the ith store, print out "NA" (without quotes) as the answer.
Constraints
 1 ≤ N ≤ 10^{9}
 1 ≤ M ≤ 3*10^{5}
 For events of type 1: 1 ≤ u ≤ v ≤ N. a, b ≤ 10^{9}
 For events of type 2: 1 ≤ u ≤ v ≤ N. a, b ≤ 10^{4}
 For events of type 3: 1 ≤ i ≤ N
Example
Input: 10 10 3 5 1 3 8 3 1 3 5 1 5 10 8 2 3 5 3 10 2 1 10 0 1 3 6 2 5 7 2 1 3 6 Output: NA 7 7 38 11 14
Explanation
 At the beginning all stores are empty so the answer for the first query which asks about the store 5 is "NA".
 The first plan of the Chef is "3 8 3 1" which means the items with price 1, 4, 7, 10, 13, 16 are added to the stores 3, 4, 5, ..., 8 correspondingly. So in the next query (asking about store 5) the answer is 7 (we have only one item to buy with no conservation fee).
 The second plan of the Chef is "5 10 8 2" so the items with price 2, 6, 14, 22, 30, 38 are added to the stores 5, 6, 7, ..., 10 correspondingly. Now the store 5 now contains two items with the corresponding prices are 7 and 2, the answer for the query about store 5 is still 7 (we still don't have any conservation fee). The store 10 contain only one item with price is 38 so the answer for the query about this store is 38.
 The first conservation fee policy is "1 10 0 1" which cause a conservation fee of 1 for each of 10 stores. The stores 6 contains 2 items, one costs 10 unit of money and the other costs 6. We need to pay 1 unit of money for the conservation fee so the largest amount of money we can spend for one item in store 6 is 10 + 1 = 11.
 The second conservation fee policy is "5 7 2 1" so a conservation fees of 1, 3, 5 are added to the stores 5, 6 and 7 correspondingly. Hence the largest amount of money we can spend for one item in store 6 is increased by 3. The answer for the last query is 14.
Note: Both of the price and the conservation fee can be negative.
Author:  tuananh93 
Editorial  http://discuss.codechef.com/problems/STREETTA 
Tags  march14, mediumhard, segmenttree, tuananh93 
Date Added:  24012014 
Time Limit:  3 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
HELP
If you are still having problems, see a sample solution here. 