Common Multiplicative Functions

Problem Description

Given a number $n$, for every $x$ from $1$ to $n$ compute $d(x), \sigma(x), \varphi(x), \mu(x)$ — the number of divisors, the sum of divisors, Euler's totient function, and the Möbius function, respectively.

To keep the output from being too large and to prevent precomputing answers from a table, you are also given $a, b$; for each function $f$ output the XOR sum of $(a \cdot x \cdot f(x) + b) \bmod 2^{32}$. For the Möbius function, treat the values as unsigned integers.

Input Format

The first line contains three integers $n, a, b$.

Output Format

Output four lines, each with one integer, representing the answers for the divisor count, the divisor sum, Euler's totient, and the Möbius function, respectively.

Sample Input

100 1 0

Sample Output

71
31663
9881
31

Constraints

For all data, $1 \leq n \leq 2 \times 10^7$, $0 \leq a, b < 2^{32}$.