Need for sum thing
You are given a triangle table of N lines. First line consists of one element, second line of three, third of ve and so on. ith line consists of 2i-1 elements. Central elements of all lines are in same coloum. So, lines form an isosceles triangle.
Each element of triangle is a number from '0' to '9'.
Problem is to respond queries with sums of elements of some triangle region of original table. Each request has a form like:
r_i, c_i, k_i
meaning that triangle of ith request has k_i lines, rst line consists of one element (r_i, c_i):
Second ine of three elements (r_i+1, c_i), (r_i+1, c_i+1), (r_i+1, c_i+2), third of ve and so on.
Find sum of all the elements from the request.
Because of a great number of queries, they are generated programmly:
A_1 = 1
A_i = (1234567·A_{i-1} + 7654321) mod 1000000007, при 2 ≤ i ≤ Q
r_i = A_i mod N + 1
c_i = A_i mod (2r_{i }- 1) + 1
k_i = A_i mod (n - r_{i }+ 1) + 1
Input
In the first line N and Q are size of original triangle and amount of requests. Then table is de ned in N lines. ith of them has exactly 2i-1 numbers, which are elements of table.
Output
Because of great number of requests, output sum of all the reports to requests.
Limits
1 ≤ N ≤ 10^3
0 ≤ Q ≤ 5·10^6