Problem Background

In this world, if something everlasting reveals its true form, it must be as majestic and unique as the elegant birds and the graceful winds and moons.

Problem Description

Given \( n \) positive integers \( a_i \) and three positive integers \( x, y, p \), a transformation on a non-negative integer \( t \) is defined as:

• Replacing \( t \) with \( (xt + y) \mod p \).

An integer \( t \) is defined as " \( k \)-invariant" if and only if its value remains unchanged after \( k \) transformations.

Xiao Ran wants to know how many numbers in the given array \( a \) are " \( k \)-invariant". To get a more accurate answer, she will provide \( q \) sets of \( k \) for queries.

Input Format

The first line contains four positive integers \( n, x, y, p \), with meanings as described in the problem.

The second line contains \( n \) positive integers, where the \( i \)-th positive integer is \( a_i \), with meanings as described in the problem.

The third line contains a positive integer \( q \), with meanings as described in the problem.

The next \( q \) lines each contain a positive integer \( k_i \), representing the query asking how many numbers in \( a \) are " \( k_i \)-invariant".

Output Format

For each query, output a single positive integer on a new line, representing the answer.

Sample Input and Output

Sample Input #1

5 2 3 7
2 3 4 5 6
5
1
2
3
4
5

Sample Output #1

1
1
5
1
1

Sample Input #2

5 3 8 4
2 3 4 5 1
5
1
2
3
4
5

Sample Output #2

1
3
1
3
1

Notes

The data guarantees that \( 1 \le n \le 10^5 \), \( 1 \le p, q \le 10^3 \), and \( 1 \le a_i, x, y, k_i \le 10^9 \).

Note that \( p \) is not necessarily a prime number.

见题面 Input 部分

见题面 Output 部分