Need for sum thing#4606

Need for sum thing

2 seconds

256 megabytes

Easy

You are given a triangular table consisting of $N$ rows. The first row has one element, the second row has three elements, the third row has five elements, and so on: the $i$ -th row contains exactly $2 i - 1$ 2i-1 elements. The central elements of all rows are aligned in one column, forming a right isosceles triangle with the right angle at the top and the hypotenuse at the bottom row.

Each element of the table is a digit from $0$ to $9$ .

Your task is to answer $Q$ queries about the table. Each query asks you to find the sum of all elements in a specified triangular region of the table. Each query is described by three numbers: $r_{i}$ r_i, $c_{i}$ c_i, $k_{i}$ k_i.

The region for the $i$ -th query is a right isosceles triangle with $k_{i}$ k_i rows and its apex at $(r_{i}, c_{i})$ (r_i, c_i). The first row of this triangle consists of the single element $(r_{i}, c_{i})$ (r_i, c_i). The second row consists of three elements: $(r_{i} + 1, c_{i})$ (r_i + 1, c_i), $(r_{i} + 1, c_{i} + 1)$ (r_i + 1, c_i + 1), and $(r_{i} + 1, c_{i} + 2)$ (r_i + 1, c_i + 2). The third row consists of five elements: $(r_{i} + 2, c_{i})$ (r_i + 2, c_i), $(r_{i} + 2, c_{i} + 1)$ (r_i + 2, c_i + 1), $\dots$ , $(r_{i} + 2, c_{i} + 4)$ (r_i + 2, c_i + 4), and so on.

Since the number of queries may be very large, they are generated programmatically as follows:

A_{1} = 1

A_1 = 1

A_{i} = (1234567 \cdot A_{i - 1} + 7654321) mod 1000000007, for 2 \leq i \leq Q

A_i = (1234567 \cdot A_{i-1} + 7654321) \bmod 1000000007, \quad \text{for } 2 \leq i \leq Q

r_{i} = A_{i} mod N + 1

r_i = A_i \bmod N + 1

c_{i} = A_{i} mod (2 r_{i} - 1) + 1

c_i = A_i \bmod (2r_i - 1) + 1

k_{i} = A_{i} mod (N - r_{i} + 1) + 1

k_i = A_i \bmod (N - r_i + 1) + 1

Input

The first line contains two integers $N$ and $Q$ ( $1 \leq N \leq 1 0^{3}$ 1 \leq N \leq 10^3, $0 \leq Q \leq 5 \cdot 1 0^{6}$ 0 \leq Q \leq 5 \cdot 10^6): the number of rows in the triangle and the number of queries.

The next $N$ lines describe the table. The $i$ -th line contains exactly $2 i - 1$ 2i-1 digits, which correspond to the elements of the $i$ -th row. There are no spaces between the digits in each row.

Output

Print the sum of answers for all the queries.

Examples

Example 1

Loading

2 i - 1

r_{i}

c_{i}

k_{i}

k_{i}

(r_{i}, c_{i})

(r_{i}, c_{i})

(r_{i} + 1, c_{i})

(r_{i} + 1, c_{i} + 1)

(r_{i} + 1, c_{i} + 2)

(r_{i} + 2, c_{i})

(r_{i} + 2, c_{i} + 1)

(r_{i} + 2, c_{i} + 4)

A_{1} = 1

A_{i} = (1234567 \cdot A_{i - 1} + 7654321) mod 1000000007, for 2 \leq i \leq Q

r_{i} = A_{i} mod N + 1

c_{i} = A_{i} mod (2 r_{i} - 1) + 1

k_{i} = A_{i} mod (N - r_{i} + 1) + 1

1 \leq N \leq 1 0^{3}

0 \leq Q \leq 5 \cdot 1 0^{6}

2 i - 1