Xor của tổng

Bạn được cho dãy số nguyên \(a\) gồm \(n\) số, đánh số từ \(1\) đến \(n\).

Khi đó bạn sẽ có \(\frac{n*(n+1)}{2}\) tổng \(a[i]+a[j]\) với (\(1 \le i \le j \le n\)).

Nhiệm vụ của bạn là tính giá trị XOR của \(\frac{n*(n+1)}{2}\) tổng này.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 5 \cdot 10^5)\) --- độ dài của mảng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((0 \leq a_i < 2^{30})\) --- các phần tử của mảng.

Output

In ra một số nguyên duy nhất, là đáp án của bài toán.

Example

3
2 4 5

14

4
6 7 3 1

3

7
2 3 5 7 9 11 13

6

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 7 & \(n \leq 2000\)

2 & 17 & \(a_i \lt 2^{10}\)

3 & 45 & \(n \leq 10^5\)

4 & 31 & Không có ràng buộc bổ sung

\hline
\endtabular