当前没有测试数据。

题目描述

There is a sequence of length n: $x_0, x_1, x_2, \ldots, x_{n-1}$. Please answer Q queries. Each query consists of one integer v, asking the minimum index i such that $x_i = v$. If the sequence doesn't have any number with value v, you only need to output -1.

Does the problem look simple? Surprise! The value of n may be as large as $10^{18}$!

Because n is so large. We will only give you four integers $x_0, a, b, p$ to generate the sequence. For all i>0, the sequence is generated as $x_i = (a \cdot x_{i-1} + b) \mod p$.

输入格式

The first line of input contains an integer T ($T \le 4$) denoting there are T tests in the input.

Each test contains Q+2 lines.

The first line of each test contains five integers $n, x_0, a, b, p$ ($ 1 \le n \le 10^{18}, 0 \le x_p,a,b < p \le 10^9 + 9 $, p is a prime number). The second line contains one integer Q ($Q \le 1000$). Each of the following Q lines contains one integer v ($0 \le v < p$).

输出格式

For each query, print one integer as the answer in one line.

样例

样例输入 1

3
1000000009 1 1 1 1000000009
5
0
1
10
1000000008
1000000007
100000009 1 1 1 1000000009
3
0
10
1000000008
1000000000000000000 1 5 0 1000000007
6
0
1
10
1000000006
12345678
1234567

样例输出 1

1000000008
0
9
1000000007
1000000006
-1
9
-1
-1
0
381838283
500000003
652614354
581802189

样例解释 1

For the first test, the sequence looks like 1, 2, 3, ..., 1000000008, 0. So the position of the first occurrence of value v is v - 1 except for value 0 which occurs at 1000000008.

样例输入 2

2
1000000000000000000 5 2 2 1000000007
4
0
1
2
3
5 1 0 3 950000017
4
0
1
2
3

样例输出 2

115068150
342074
115068151
-1
-1
0
-1
1