题目描述

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

设总共有 $p$ 个参加抽奖的志愿者，开始时每一个志愿者领取一个 $0$ 到 $p-1$ 的号码。任意两个志愿者领取的号码不同。屏幕的正中央是五福娃的头像，他们不停的眨眼欢迎大家。开始抽奖时，工作人员按下屏幕旁边的按钮，等待屏幕上的画面静止下来。这时，福娃们都停止眨眼了。当然，画面静止时，有的福娃的眼睛可能是睁开的，有的是闭上的。如果所有福娃的眼睛都闭上了，工作人员需要重新按一下按钮。这样，直到至少有一个福娃的眼睛是睁开的。接着，工作人员开始观察有哪些福娃的眼睛是睁开的。

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

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

用 $L$ 表示所有数字的集合，例如，如果贝贝、晶晶的眼睛是睁开的，欢欢、迎迎、妮妮的眼睛是闭上的，则 $L= \{ 2,3,4,6,8,9,12,\dots \}$。令 $l(x)$ 表示第 $x$ 大的幸运数字。例如，上面的例子中，$l(1)=2，l(4)=6$ 等等。接着，工作人员开始随机产生两个数，小的数是 $a$，大的数字是 $b$。定义集合 $T(a,b)$ 为：

（其中 表示x整除y） 定义一个自然数的有限子集的特征值 $f$ 如下：

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

其中，$S \backslash d$ 表示把 $S$ 删除元素 $d$ 后的集合，$q$ 是一个给定的非负整数。在 $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 0 0 1 0
10001 2
3
1 10
2 12
4 15

3265
5816
0

数据规模与约定

$1 \le a \le b \le 10^5,n \le 10^5$。

$p,q \le 2 \times 10^9$。

提示