常见积性函数

题目描述

给一个数字$n$，求$1\sim n$中的所有数$x$的$d(x),\sigma(x),\varphi(x),\mu(x)$，分别表示因子个数，因子和，欧拉函数，莫比乌斯函数。

为了防止输出过大和防止打表，给定$a, b$，输出每个函数$f$，分别求出$(a\cdot x\cdot f(x)+b)\bmod 2^{32}$的异或和。对于莫比乌斯函数，按照无符号整型处理。

输入格式

第一行三个整数$n, a, b$。

输出格式

四行，四个整数，分别表示因子个数，因子和，欧拉函数，莫比乌斯函数对应的答案。

样例输入

100 1 0

样例输出

71
31663
9881
31

数据范围

对于所有数据，保证$1\leq n\leq 2\times 10^7, 0\leq a,b< 2^{32}$。