说明

在"星火征途"的密码破译任务中，红军截获了一个数列的异或结果。现在需要计算从1到N这N个连续自然数的异或结果。 即计算：1 xor 2 xor 3 xor ... xor N 请你编写程序，输出这个结果。

输入格式

输入共1行，一个正整数N。

输出格式

输出共1行，一个整数，表示1 xor 2 xor 3 xor ... xor N的结果。

5

1

提示

对于所有数据，1 ≤ N ≤ 10^12。直接循环会超时，请找规律： - N%4==0：结果为N - N%4==1：结果为1 - N%4==2：结果为N+1 - N%4==3：结果为0

来源

改编自PPT课件《计算机基础知识：位运算》数列之异或（洛谷P3908）