Tổng XOR mảng

Cho mảng \(A\) gồm \(n\) số nguyên. Định nghĩa hàm \(f(l, r)\) là: \(A_l\) \(OR\) \(A_{l+1}\) \(\ldots\) \(OR\) \(A_r\). Tính tổng XOR của mọi \(f(l, r)\) với \(1 \le l \le r \le n\).

Input

• Dòng đầu tiên gồm số nguyên \(n\) (\(1 \le n \le 10^6\)).

• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(0 \le A_i \le 10^9\)).

Output

In ra kết quả.

Example

Input:

3
1 4 3

Output:

3

Note

Với \(n = 3\), \(A = [1, 4, 3]\):
\(f(1,1) = 1\), \(f(1,2) = 1\ OR\ 4 = 5\), \(f(1,3) = 1\ OR\ 4\ OR\ 3 = 7\), \(f(2,2) = 4\), \(f(2,3) = 4\ OR\ 3 = 7\), \(f(3,3) = 3\).

Tổng XOR của tất cả các giá trị trên: \(1 \oplus 5 \oplus 7 \oplus 4 \oplus 7 \oplus 3 = 3\).