Count the number of ones in bit repesentation of number.

Generate N number using formula (a*i+b)%c for all 1<=i<=n

limit: 1<=N<=1000000

0<=a*N, b*N<2^64

1<=c<2^64

Input

N

a b c

Output

[N numbers]

c1

c2

..

cn

Example

Input:
5
5 6 7

Output:
1
1
0
2
2

Explanation
Generated numbers are 4, 2, 0, 5, 3 and bit counts are 1, 1, 0, 2, 2 respectively

hints:
use unsigned long long