With 90 days remaining until the opening of the 2008 Beijing Olympics, CTSC is preparing a lottery for volunteers. As a volunteer, you are naturally looking forward to this event.

The CTSC committee has introduced the rules for the lottery. Suppose there are a total of $p$ volunteers participating in the lottery, and each volunteer is initially assigned a unique number from $0$ to $p-1$. In the center of the screen are the avatars of the five Fuwa, who blink continuously to welcome everyone. When the lottery begins, a staff member presses a button next to the screen and waits for the image on the screen to stop. At this point, the Fuwa stop blinking. Of course, when the image stops, some Fuwa may have their eyes open, while others have them closed. If all the Fuwa have their eyes closed, the staff member must press the button again. This continues until at least one Fuwa has its eyes open. Then, the staff member observes which Fuwa have their eyes open.

The staff member has assigned labels to the five Fuwa: Beibei, Jingjing, Huanhuan, Yingying, and Nini are labeled 2, 3, 4, 5, and 6, respectively (the staff considers 0 and 1 to be "unlucky" numbers). Lucky numbers are defined as follows:

1. If a Fuwa's eyes are open, its corresponding label is a lucky number.
2. If numbers $l_1$ and $l_2$ (which may be equal) are both lucky numbers, then their product $l_1 \times l_2$ is also a lucky number.
3. No other numbers are lucky numbers.

Let $L$ denote the set of all lucky numbers. For example, if the eyes of Beibei and Jingjing are open, and the eyes of Huanhuan, Yingying, and Nini are closed, then $L = \{2, 3, 4, 6, 8, 9, 12, \dots\}$. Let $l(x)$ denote the $x$-th smallest lucky number. For example, in the case above, $l(1) = 2$, $l(4) = 6$, and so on.

Next, the staff member randomly generates two numbers, the smaller of which is $a$ and the larger is $b$. Define the set $T_{a,b}$ as: $$T_{a,b} = \{d \mid d \in L, l(a) \mid d, d \mid l(b)\}$$ (where $x \mid y$ denotes that $x$ divides $y$).

Define the characteristic value $f$ of a finite subset of natural numbers as follows: 1. The characteristic value of the empty set is 0, i.e., $f(\emptyset) = 0$. 2. For a non-empty set $S$, let $d$ be the minimum element in $S$. Then: $$f(S) = d + f(S \setminus \{d\}) + q \times d \times f(S \setminus \{d\})$$ where $S \setminus {d}$ denotes the set $S$ with the element $d$ removed, and $q$ is a given non-negative integer.

After $a$ and $b$ are generated, the winning volunteer is determined; their number is the remainder of $f(T_{a,b})$ divided by $p$. The staff member will generate multiple pairs of $a$ and $b$, thus forming multiple winners. However, the program at the lottery site takes a very long time to calculate the winning volunteers. Out of eager anticipation for the results, you decide to rewrite the calculation program.

Input

The first line contains 5 space-separated numbers, each being 0 or 1, representing whether the eyes of Beibei, Jingjing, Huanhuan, Yingying, and Nini are open, respectively. 0 corresponds to eyes closed, and 1 corresponds to eyes open. The 5 numbers cannot all be 0.

The second line contains two space-separated numbers, $p$ and $q$, where $p$ is the number of volunteers participating in the lottery, and $q$ is used to calculate the characteristic value of the set as described above.

The third line contains the number $n$, representing the number of times $a$ and $b$ are drawn.

The next $n$ lines each contain two space-separated numbers $a$ and $b$, representing the two numbers generated in one lottery draw.

Output

Output $n$ lines, each containing an integer representing the number of the winner for that draw. The order must correspond one-to-one with the $n$ pairs of $a$ and $b$ provided in the input. Of course, one person may win multiple times.

Examples

Input 1

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

Output 1

3265
5816
0

Note

Beibei and Yingying's eyes are open, so the first 15 lucky numbers are 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125. $l(1) = 2$, $l(10) = 40$. The lucky numbers that are both multiples of 2 and divisors of 40 are 2, 4, 8, 10, 20, 40. Thus $T_{1,10} = \{2, 4, 8, 10, 20, 40\}$. The calculation process for the characteristic value of $T_{1,10}$ is:

$f(\emptyset) = 0$ $f(\{40\}) = 40 + 0 + 2 \times 40 \times 0 = 40$ $f(\{20, 40\}) = 20 + 40 + 2 \times 20 \times 40 = 1660$ $f(\{10, 20, 40\}) = 10 + 1660 + 2 \times 10 \times 1660 = 34870$ $f(\{8, 10, 20, 40\}) = 8 + 34870 + 2 \times 8 \times 34870 = 592798$ $f(\{4, 8, 10, 20, 40\}) = 4 + 592798 + 2 \times 4 \times 592798 = 5335186$ $f(\{2, 4, 8, 10, 20, 40\}) = 2 + 5335186 + 2 \times 2 \times 5335186 = 26675932$

Therefore, the winner's number is the remainder of 26675932 divided by 10001, which is 3265. Similarly, $T_{2,12} = \{4, 8, 16, 32, 64\}$, its characteristic value is 21167932, and the remainder when divided by 10001 is 5816. Also, $T_{4,15} = \emptyset$.

Constraints

For 20% of the data points: $1 \le a \le b \le 1000$, $n \le 2000$;

For all data points: $1 \le a \le b \le 100000$, $n \le 100000$, $p, q \le 2 \times 10^9$.

60% of the data points satisfy: $p$ is a prime number.