题目背景
众所周知，可以用一些简单的算法来生成伪随机序列。然而，某些这样的算法并不靠谱，因为生成的数据可以被快速预测。如下我们将给出一种伪随机算法，使得我们能快速预测序列中的值。
题目描述
给定一个整系数多项式 $P(x)$。递归定义数列 $\{a_n\}_{n\geq 0}$ 如下：$a_0=M,a_{n+1}=P(a_n) \bmod 2^{64}$。
有 $q$ 次询问，分为两种：
- 给定 $n$，求 $a_n$。
- 给定 $x$，求最小的 $n$ 使得 $a_n=x$，或者判断无解。
$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$，其中 $p_i$ 为 $P$ 的系数。
输入格式
从标准输入读入数据。
输入第一行包含两个整数 $\deg$（$1 \le \deg \le 10^5$），$M$（$0 \le M \le 2^{64}-1$），分别表示多项式 $P$ 的次数和 $a_0$ 的值。
第二行输入 $P+1$ 个小于 $2^{64}$ 的非负整数 $p_0,p_1,\dots,p_{\deg}$ 表示 $P$ 的 $0,1,\dots,\deg$ 次项系数。
第三行输入一个正整数 $q$（$1 \le q \le 5\times 10^3$），表示询问的个数。
接下来 $q$ 行，每一行两个整数 $opt$（$1 \le opt \le 2$），$x$（$0 \le x \le 2^{64}-1$）表示一组询问。
- 对于 $opt=1$：这个询问要求 $a_x$ 的值。
- 对于 $opt=2$：这个询问要求满足 $a_n=x$ 的最小的 $n$。
输出格式
输出到标准输出。
对于每一组询问，输出一行一个整数，表示这组询问的答案。
对于无解的询问，输出 -1。
样例
输入
1 0
1 1
2
1 100
2 100输出
100
100解释
$P(x)=x+1,a_n=n$。
样例二
见下载目录下的 ex_2.in 与 ex_2.ans。
子任务
下面的 $M$ 表示第一类询问中的 $n$ 的最大值。
子任务 $1$（$5$ 分）：$M \le 10^6$，$opt=1$。
子任务 $2$（$7$ 分）：$\deg =1,p_0=0$。
子任务 $3$（$8$ 分）：$\deg =1$。
子任务 $4$（$15$ 分）：$opt=1$。
子任务 $5$（$15$ 分）：$\deg =2$。
子任务 $6$（$50$ 分）：无额外限制。