Description

Given a function $f$ satisfying $f(1)=1$, and

Given a positive integer $n$, compute the values $f(1), f(2), \cdots, f(n)$. To control the output size, you only need to output the value of the following expression:

Here $\oplus$ denotes xor.

Input Format

One line with a positive integer $n$.

Output Format

One line with a non-negative integer, representing the value of $\bigoplus_{k=1}^n\left(f(k)\bmod 2^{32}\right)$.

10

10

1000000

3527171714

10000000

191685100

Hint

For all testdata, $1 \le n \le 5 \times 10^7$.

For Sample 1, the first $10$ terms of $f$ are: $1, 1, 2, 3, 4, 6, 6, 9, 10, 12$.

The time limit is $1.5$ times that of std.

Translated by ChatGPT 5