generator 2

题号：NC51484
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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 () denoting there are T tests in the input.

Each test contains Q+2 lines.

The first line of each test contains five integers  (, p is a prime number).
The second line contains one integer Q ().
Each of the following Q lines contains one integer v ().

输出描述:

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

输出

复制

说明

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

输出

复制