Mobius Inversion

Problem Description

Given a function $f(1), f(2), \dots, f(n)$ and the relation $f(n)=\sum_{d|n} g(d)$, find $g(1), g(2), \dots, g(n)$.

Input Format

The first line contains four integers $n(1\leq n\leq 10^6), A, B, C(0\leq A, B, C < 2^{32})$.

To avoid overly large input, $f$ is generated by the following code:

unsigned int A,B,C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%u%u%u", &n, &A, &B, &C);
    for (int i = 1; i <= n; i++)
        f[i] = rng61();
}

Output Format

To avoid overly large output, output the XOR sum of all elements of $g$ after converting each of them to a 32-bit unsigned integer.

Sample Input

10 1 2 3

Sample Output

4289023889