U529592 解密(decode)

小明有 $n$ 个非负数，为了不让别人知道，他将这 $n$ 个数进行了加密......

已知这 $n$ 个数为 $a_1,a_2......a_n$ ，小明将其加密成序列 $b_1,b_2......b_{n-1}$ 。 加密方式如下：即其加密参数为 $p,q$ ，则对于任意 $1\le i \le n-1$ ，若 $i$ 为奇数，有 $b_i=pa_i+qa_{i+1}$ ，若 $i$ 为偶数，有 $b_i=qa_i+pa_{i+1}$ 。 现在小红看到了小明记下的所有信息，但仍无法算出加密前的 $a$ 数组，她会问你 $k$ 个问题，每个问题形如：若 $a_x$ 为整数，那么 $a_y$ 有多少种取值？

第一行三个数 $n,p,q$ 。 第二行 $n-1$ 个数，第 $i$ 个数表示 $b_i$ 。 第三行 $k$ 个数，之后每行两个数，表示一个询问的 $x,y$ 。

共 $k$ 行，每行表示一个询问的答案，若 $a_y$ 可以有无限种取值，输出 "INF" （不包含双引号）。

| 测试点编号 | $n\le$ | $k\le$ | | :-----------: | :-----------: | :-----------: | | $1 \sim 6$ | $100$ | $100$ | | $7 \sim 12$ | $10^5$ | $5$ | | $13 \sim 20$ | $10^5$ | $10^5$ | 对于 $100\%$ 的数据，保证 $|b_i|,|p|,|q| \le 10^9$ 且为整数