[CTSC2008] 奥运抽奖

题目描述

距 $2008$ 年北京奥运会开幕还有90天时，CTSC 准备为志愿者们举行一次抽奖活动。作为志愿者的一员，你对这次抽奖活动自然是万分期待。

CTSC 委员会介绍了抽奖活动的规则。设总共有 $p$ 个参加抽奖的志愿者，开始时每一个志愿者领取一个 $0 \sim p-1$ 的号码。任意两个志愿者领取的号码不同。

屏幕的正中央是五福娃的头像，他们不停的眨眼欢迎大家。开始抽奖时，工作人员按下屏幕旁边的按钮，等待屏幕上的画面静止下来。这时，福娃们都停止眨眼了。

当然，画面静止时，有的福娃的眼睛可能是睁开的，有的是闭上的。如果所有福娃的眼睛都闭上了，工作人员需要重新按一 下按钮。这样，直到至少有一个福娃的眼睛是睁开的。接着，工作人员开始观察有哪些福娃的眼睛是睁开的。

工作人员对五个福娃都标了号。贝贝、晶晶、欢欢、迎迎、妮妮的标号分别是 $2$、$3$、$4$、$5$、$6$（工作人员认为 $0$ 和 $1$ 都不是好数字）。定义幸运数字如下：

• 如果一个福娃的眼睛是睁开的，那么他（她）对应的标号就是幸运数字；
• 如果数字 $l_1$ 和 $l_2$（可能相等）都是幸运数字，那么他们的乘积也是幸运数字；
• 其他的数字都不是幸运数字。

用 $L$ 表示所有数字的集合，例如，如果贝贝、晶晶的眼睛是睁开的，欢欢、迎迎、妮妮的眼睛是闭上的，则 $L=\{2,3,4,6,8,9,12,…\}$。令 $l(x)$ 表示第 $x$ 大的幸运数字。例如，上面的例子中，$l(1)=2$，$l(4)=6$ 等等。

接着，工作人员开始随机产生两个数，小的数是 $a$，大的数字是 $b$。定义集合 $T_{a,b}$ 为：$T_{a,b}=\{d|d∈L,l(a)|d,d|l(b)\}$（其中 $x|y$ 表示 $x$ 整除 $y$ ）

定义一个自然数的有限子集的特征值 $f$ 如下：

• 空集的特征值为$0$。
• 对于非空集合 $S$，令 $d$ 为 $S$ 中的最小元素，则

$$f(S)=d+f(S\backslash d)+q\times d\times f(S\backslash d)$$

其中， $S\backslash d$ 表示把 $S$ 删除元素 $d$ 后的集合，$q$ 是一个给定的非负整数。

在 $a$ 和 $b$ 产生以后，中奖的志愿者就确定了，他的号码是 $f(T_{a,b})$ 除以 $p$ 的余数。工作人员会产生多次 $a$，$b$，这样就能形成多个中奖者。

但是，抽奖现场的程序需要很长的时间才能算出中奖的志愿者。出于对中奖结果的热切期待，你便想要重新写一下计算程序，于是，你的目光移向了前面的键盘……。

输入格式

输入的第一行给出用空格隔开的五个数，每个数不是 $0$ 就是 $1$，分别表示贝贝、晶晶、欢欢、迎迎、妮妮的眼睛是否睁开。$0$ 对应眼睛闭上，$1$ 对应眼睛睁开。$5$ 个数不可能都是 $0$。

第二行给出了用空格隔开的两个数，$p$ 和 $q$。 其中 $p$ 表示参加抽奖的志愿者的人数，$q$ 如前所述，用来计算集合的特征值。

第三行给出了数 $n$，表示抽取的 $a$ 和 $b$ 的次数。

接下来的 $n$ 行，每一行有两个数 $a$、$b$，中间用空格隔开，表示一次抽奖产生的两个数。

输出格式

输出共 $n$ 行，每一行一个整数，表示一次抽奖中中奖者的号码。顺序与输入的 $n$ 对 $a$、$b$ 一一对应。当然，一个人可能中奖多次。

样例 #1

样例输入 #1

1 0 0 1 0
10001 2
3
1 10
2 12
4 15

样例输出 #1

3265
5816
0

提示

【样例说明】

贝贝和迎迎的眼睛是睁开的，因此，前面 $15$ 个幸运数字是 $2$、$4$、$5$、$8$、$10$、$16$、$20$、$25$、$32$、$40$、$50$、$64$、$80$、$100$、$125$。

$l(1) = 2$，$l(10) = 40$。既是 $2$ 的倍数，又是 $40$ 的约数的幸运数字有 $2$、$4$、$8$、$10$、$20$、$40$。 所以 $T_{1,10} = \{2,4,8,10,20,40\}$。$T_{1,10}$ 的特征值的计算过程为：

$f(\emptyset )=0$

$f(\{40\})=40+0+2\times40\times0=40$

$f(\{20,40\})=20+40+2\times20\times40=1660$

$f(\{10,20,40\})=10+1660+2\times10\times1660=34870$

$f(\{8,10,20,40\})=8+34870+2\times8\times34870=592798$

$f(\{4,8,10,20,40\})=4+592798+2\times4\times592798=5335186$

$f(\{2,4,8,10,20,40\})=2+5335186+2\times2\times5335186=26675932$

所以中奖者的号码就是 $26675932$ 除以 $10001$ 的余数 —— $3265$。 类似的，$T_{2,12} = \{4,8,16,32,64\}$，它的特征值是 $21167932$，除以 $10001$ 的余数是 $5816$。而 $T_{4,15} = \emptyset$。

【数据规模】 对于 $20\%$ 数据，$1 ≤ a ≤ b ≤1000$，$n ≤ 2000$； 对于 $60\%$ 的数据，$p$ 为素数； 对于 $100\%$ 的数据，$1 ≤ a ≤ b ≤ 10^5$，$n ≤ 10^5$，$p, q ≤ 2 \times 10^9$。