Score : 600 points
We have a sequence of k numbers: d_0,d_1,...,d_{k - 1}.
Process the following q queries in order:
Here (y~\textrm{mod}~z) denotes the remainder of y divided by z, for two integers y and z~(z > 0).
Input is given from Standard Input in the following format:
k q d_0 d_1 ... d_{k - 1} n_1 x_1 m_1 n_2 x_2 m_2 : n_q x_q m_q
Print q lines.
The i-th line should contain the response to the i-th query.
3 1 3 1 4 5 3 2
1
For the first query, the sequence {a_j} will be 3,6,7,11,14.
Thus, the response to this query should be 1.
7 3 27 18 28 18 28 46 1000000000 1000000000 1 7 1000000000 2 10 1000000000 3 12
224489796 214285714 559523809