Counting K-Invariant Numbers

You are given an array of n positive integers \(a_1,a_2,\dots,a_n\) and three positive integers \(x, y, p\). Define a transformation on any nonnegative integer \(t\) as follows:

\[ t \to (x \cdot t + y) \bmod p, \]

A number \(t\) is called k-invariant if after applying the transformation exactly \(k\) times, the number remains unchanged, i.e., if \(f^{k}(t) = t\).

Your task is to answer \(q\) queries. In each query, a value \(k\) is provided and you have to determine how many numbers in the given array are \(k\)-invariant under the above transformation.

Note:

• If \(x \not\equiv 1 \pmod{p}\), then the \(k\)th iterate of \(t\) can be expressed in closed form as \[ f^k(t) \equiv x^k \cdot t + y \cdot \frac{x^k - 1}{x - 1} \pmod{p}, \] and the invariant condition \(f^k(t)=t\) leads to a linear congruence.
• If \(x \equiv 1 \pmod{p}\), then \(f(t)=t+y\) and \(f^k(t)=t+k\cdot y\) so \(t\) is invariant if and only if \(k\cdot y \equiv 0 \pmod{p}\).

inputFormat

The first line contains five integers: \(n\), \(q\), \(x\), \(y\) and \(p\) (where \(p\) is a prime number).

The second line contains \(n\) positive integers \(a_1,a_2,\dots,a_n\).

Each of the next \(q\) lines contains one integer \(k\), representing a query.

outputFormat

For each query, output a single line containing one integer, which is the count of \(k\)-invariant numbers in the array.

sample

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

1
1
5