题目描述

已知函数 $f$ 满足 $f(1)=1$，且

给定正整数 $n$，试求出 $f(1),f(2),\cdots,f(n)$ 的值。为控制输出量，你只需输出下式的值：

其中 $\oplus$ 代表异或。

输入格式

一行一个正整数 $n$。

输出格式

一行一个非负整数，代表 $\bigoplus_{k=1}^n\left(f(k)\bmod 2^{32}\right)$ 的值。

10

10

1000000

3527171714

10000000

191685100

提示

对于所有数据，$1\le n\le 5\times 10^7$。

对于样例一，$f$ 的前 $10$ 项依次为：$1,1,2,3,4,6,6,9,10,12$。

时限为 std 的 1.5 倍。