Problem D
Linear Recurrences

Input

The first line of input contains an integer $1 \le N \le 40$, the degree of the recurrence. The next line of input contains $N+1$ integers $a_0, a_1, \ldots , a_ N$ indicating that the linear recurrence is $x_{t} = a_0 + \sum _{i=1}^ N a_ i x_{t-i}$. The next line contains $N$ integers $x_0, \ldots , x_{N-1}$ giving the initial values for the recursion. All the coefficients $a_0, \ldots , a_ N$ and initial values $x_0, \ldots , x_{N-1}$ are integers between $-10^9$ and $10^9$ (inclusive).

The next line contains an integer $1 \le Q \le 10$, the number of queries. Then follow $Q$ lines of queries. Each query consists of two integers $T$, $M$ where $0 \le T \le 10^{18}$ gives the index and $1 \le M \le 10^{9}$ is a moduli.

Output

For each query $T$, $M$, output a line containing $x_ T \bmod M$.

2
0 1 1
0 1
6
1 100000
2 100000
3 100000
4 100000
5 100000
6 100000

1
1
2
3
5
8

2
5 7 9
36713 5637282
4
1 10000
1375 1
3781 23
34683447233 1571385

7282
0
16
299255

3
1 2 3 4
0 0 0
1
42424242424242 1000000

552200