The input consists of at most 50 datasets. Each dataset is represented by a line containing four integers N, S, W, and Q, separated by spaces, where 1 ≤ N ≤ 10^5, 1 ≤ S ≤ 10^9, 1 ≤ W ≤ 10^9, and Q is a prime number less than 10^8. The sequence a0 · · · aN−1 of length N is generated by the following code, in which ai is written as a[i].
int g = S;
for(int i=0; i < N; i++)
{
a[i] = (g/7) % 10;
if( g%2 == 0 ) { g = (g/2); }
else { g = (g/2) ^ W; }
}
Note: the operators /, %, and ^ are the integer division, the modulo, and the bitwise exclusiveor, respectively. The above code is meant to be a random number generator. The intended solution does not rely on the way how the sequence is generated.
The end of the input is indicated by a line containing four zeros separated by spaces.