Count the number of ones in bit representation 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⁶⁴

1 ≤ c < 2⁶⁴

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.

hint: use unsigned long long.