SPOJ.com - Problem RPAR

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² + bx + c. The ground can be defined as a line with N blocks, numbered from 0 to N-1, 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₀, x₁] in which the next parabola will fall, and the function of our parabola is f(x) (defined above), some block i (x₀ <= i <= x₁), 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₀, x₁], we're looking for the sum of h_i for all i (x₀ <= i <= x₁) 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₀ x₁ a b c (0 <= x₀ <= x₁ < N, 0 <= a, b, c <= 10006, all integers)
this type of query just tells you that a parabola has fallen into the interval [x₀, x₁], and its function is f(x) = ax² + bx + c
1 x₀ x₁ (0 <= x₀ <= x₁ < 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₀, x₁] 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)

Submit solution!

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

hide comments



2021-07-31 20:44:07 Finally done, nice problem ..
2013-12-31 01:55:48 J. Rewieñski I have a serious problem with this problem. 1. I wrote a brute-force solution. (of course TLE but that was suspected) 2. I wrote second version, it generates same reesults, but now I get WA. I checked it many times I don't know where's my mistake. I think I do not understand the task well. I mean, I really don't see a mistake there, can anybody help? (just verify my brute force solution) Edit: Well, you must be really careful with the Mod Last edit: 2014-03-29 03:33:38
2013-07-20 20:35:56 Aman Gupta phew!
2012-05-30 13:55:51 :D 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.
2012-05-29 11:55:33 :D try on ideone.com I found it fails more often in case of memory corruptions. P.S. This must be funniest intro to a problem I've ever read. :D Last edit: 2012-05-30 18:08:19
2011-08-22 15:27:49 Seshadri R 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 answer: there are no blank lines between the queries. Last edit: 2010-07-09 21:11:14