RPAR  Raining Parabolas
Nowadays you just can't predict what'll fall on your head the next day.. Because we don't care about the nature, it is now striking back: it's raining parabolas!
The parabolas that are falling are given in form of quadratic functions: f(x) = ax^{2} + bx + c. The ground can be defined as a line with N blocks, numbered from 0 to N1, initially having height 0. At some point, a block can have some positive height, but when it exceeds 10006 (we don't actually know why, but measurements have shown it is a weird regularity) it falls back to 0. When a parabola falls on some block, it interacts with its current configuration (the parabolas that have fallen there before it) by summing with it. More precisely, if we are given an interval [x_{0}, x_{1}] in which the next parabola will fall, and the function of our parabola is f(x) (defined above), some block i (x_{0} <= i <= x_{1}), with height h_{i}, the new height of that block becomes (h_{i} + f(i)) modulo 10007.
Today you somehow came in possession of some sort of schedule which defines the order in which the parabolas will fall on the ground. Apart from that, you're interested total heights (sums of heights) of consecutive blocks of ground. When we want to find the total height of some interval [x_{0}, x_{1}], we're looking for the sum of h_{i} for all i (x_{0} <= i <= x_{1}) modulo 10007.
Before the first parabola falls, the ground is flat (all heights are 0).
Input
The first line of input contains two integers: N and M (1 <= N, M <= 100000). N specifies the number of blocks on the floor, and M is the number of queries. Each of the next M lines contains a query. As we already said, we have two types of queries of form:
 0 x_{0} x_{1} a b c (0 <= x_{0} <= x_{1} < N, 0 <= a, b, c <= 10006, all integers)
this type of query just tells you that a parabola has fallen into the interval [x_{0}, x_{1}], and its function is f(x) = ax^{2} + bx + c  1 x_{0} x_{1} (0 <= x_{0} <= x_{1} < N, all integers)
this is the type of query you have to answer  output the sum of heights of all the blocks from interval [x_{0}, x_{1}] modulo 10007.
Output
For each query of type 1, output a single line containing the sum of all the heights in the given interval modulo 10007.
Example
Input: 10 2 0 0 9 1 0 0 1 0 3 Output: 14
(the sum of the first 4 squares (from 0 to 3) is 14)
hide comments
nikhil0010:
20210731 20:44:07
Finally done, nice problem .. 

J. RewieĆ±ski:
20131231 01:55:48
I have a serious problem with this problem.


Aman Gupta:
20130720 20:35:56
phew! 

:D:
20120530 13:55:51
There aren't any "tricky cases" for this problem. Simply because it has a trivial brute force solution. You can count it in O(N*M) time (O(N) per query/operation) using array of size N. Use that to check your output values. 

:D:
20120529 11:55:33
try on ideone.com I found it fails more often in case of memory corruptions.


Seshadri R:
20110822 15:27:49
Is there a blank line before every query? There is no mention of this in the explanation, but the Example input has interleaving blank lines

Added by:  gustav 
Date:  20100705 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 
Resource:  own problem 