1280. Compute XOR from 1 to N

Given a non-negative integer n, compute the XOR of all integers from 1 to n inclusive (1 ^ 2 ^ ... ^ n). Use the well-known period-4 pattern instead of looping. If n is 0 the result is 0.

Input: A JSON object {"n": <non-negative integer>}.

Output: Return the XOR of 1..n as an integer.

Examples

Input: {"n":6}
Output: 7
Explanation: 6 mod 4 = 2, so the answer is n+1 = 7.

Input: {"n":7}
Output: 0
Explanation: 7 mod 4 = 3, so the running XOR resets to 0.

Constraints

• 0 <= n <= 10^15

Asked by