Background

As is well known, pseudo-random sequences can be generated using simple algorithms. However, some such algorithms are unreliable because the generated data can be predicted quickly. Below, we present a pseudo-random algorithm that allows us to quickly predict the values in the sequence.

Description

Given an integer-coefficient polynomial $P(x)$, the sequence $\{a_n\}_{n\geq 0}$ is defined recursively as follows: $a_0=M, a_{n+1}=P(a_n) \bmod 2^{64}$.

There are $q$ queries, divided into two types:

• Given $n$, find $a_n$.
• Given $x$, find the smallest $n$ such that $a_n=x$, or determine that no such $n$ exists.

$1 \le \deg P \le 10^5$, $1 \le q \le 5\times 10^3$, $0 \le x,n,p_i \le 2^{64}-1$, where $p_i$ are the coefficients of $P$.

Input

Read data from standard input.

The first line contains two integers $\deg$ ($1 \le \deg \le 10^5$) and $M$ ($0 \le M \le 2^{64}-1$), representing the degree of the polynomial $P$ and the value of $a_0$, respectively.

The second line contains $\deg+1$ non-negative integers less than $2^{64}$, $p_0, p_1, \dots, p_{\deg}$, representing the coefficients of the $0, 1, \dots, \deg$-th degree terms of $P$.

The third line contains a positive integer $q$ ($1 \le q \le 5\times 10^3$), representing the number of queries.

The next $q$ lines each contain two integers $opt$ ($1 \le opt \le 2$) and $x$ ($0 \le x \le 2^{64}-1$), representing a query.

• For $opt=1$: This query asks for the value of $a_x$.
• For $opt=2$: This query asks for the smallest $n$ such that $a_n=x$.

Output

Output to standard output.

For each query, output one integer per line representing the answer to that query.

For queries with no solution, output -1.

Examples

Input

1 0
1 1
2
1 100
2 100

Output

100
100

Note

$P(x)=x+1, a_n=n$.

Example 2

See ex_2.in and ex_2.ans in the download directory.

Subtasks

In the following, $M$ denotes the maximum value of $n$ in the first type of query.

Subtask 1 (5 points): $M \le 10^6$, $opt=1$.

Subtask 2 (7 points): $\deg =1, p_0=0$.

Subtask 3 (8 points): $\deg =1$.

Subtask 4 (15 points): $opt=1$.

Subtask 5 (15 points): $\deg =2$.

Subtask 6 (50 points): No additional constraints.