There is a party in town and you would like to attend it. The party theme is bitwise operations! You just knocked on the door and the bodyguard with a big xor-like hat on his head asks you a question in order to let you in. You just heard your favourite song "Se misca pe bit" playing inside, so you need to solve the problem as quick as possible.
You are given a sequence of $1 <= N <= 10^6$ pairwise _distinct_ non-negative integers $a_1, a_2,..., a_N$. The value of a subsequence $a_i, a_{i + 1},..., a_j$ with $i <= j$ is:
where OR is the bitwise OR operator.
You need to calculate the bitwise XOR sum of the values of all subsequences.
The first line of the input will contain the number $N$ ($1 <= N <= 10^6$), representing the size of the given sequence $a$. The following line will contain $N$ pairwise _distinct_ non-negative integers (the array $a$), where $0 <= a_i <= 10^(18)$ for $1 <= i <= N$.
You should output one line containing one non-negative integer: the bitwise XOR sum of the values of all subsequences.
The value of subsequence:
$[ 2 ]$ is $2 " "upright(O R) " "2 = 2$
$[ 2, 1 ]$ is $2 " "upright(O R) " "1 = 3$
$[ 2, 1, 5 ]$ is $5 " "upright(O R) " "1 = 5$
$[ 2, 1, 5, 7 ]$ is $7 " "upright(O R) " "1 = 7$
$[ 1 ]$ is $1 " "upright(O R) " "1 = 1$
$[ 1, 5 ]$ is $5 " "upright(O R) " "1 = 5$
$[ 1, 5, 7 ]$ is $7 " "upright(O R) " "1 = 7$
$[ 5 ]$ is $5 " "upright(O R) " "5 = 5$
$[ 5, 7 ]$ is $7 " "upright(O R) " "5 = 7$
$[ 7 ]$ is $7 " "upright(O R) " "7 = 7$
And the XOR sum of these values is $5$.
## Input
The first line of the input will contain the number $N$ ($1 <= N <= 10^6$), representing the size of the given sequence $a$. The following line will contain $N$ pairwise _distinct_ non-negative integers (the array $a$), where $0 <= a_i <= 10^(18)$ for $1 <= i <= N$.
## Output
You should output one line containing one non-negative integer: the bitwise XOR sum of the values of all subsequences.
[samples]
## Note
The value of subsequence: $[ 2 ]$ is $2 " "upright(O R) " "2 = 2$ $[ 2, 1 ]$ is $2 " "upright(O R) " "1 = 3$ $[ 2, 1, 5 ]$ is $5 " "upright(O R) " "1 = 5$ $[ 2, 1, 5, 7 ]$ is $7 " "upright(O R) " "1 = 7$ $[ 1 ]$ is $1 " "upright(O R) " "1 = 1$ $[ 1, 5 ]$ is $5 " "upright(O R) " "1 = 5$ $[ 1, 5, 7 ]$ is $7 " "upright(O R) " "1 = 7$ $[ 5 ]$ is $5 " "upright(O R) " "5 = 5$ $[ 5, 7 ]$ is $7 " "upright(O R) " "5 = 7$ $[ 7 ]$ is $7 " "upright(O R) " "7 = 7$ And the XOR sum of these values is $5$.
**Definitions**
Let $ n \in \mathbb{Z} $, $ t \in \mathbb{Z}_{\geq 0} $.
Let $ X = (x_1, x_2, \dots, x_n) $ be a strictly increasing sequence of distinct integers with $ x_1 < x_2 < \dots < x_n $, and $ x_i \in [-10^9, 10^9] $.
Your position starts at $ 0 $.
**Constraints**
1. $ 1 \leq n \leq 200000 $
2. $ 0 \leq t \leq 10^9 $
3. $ x_1 < x_2 < \dots < x_n $
**Objective**
Find the maximum number $ k \in \{0, 1, \dots, n\} $ such that there exists a subset of $ k $ bonuses at positions $ \{x_{i_1}, x_{i_2}, \dots, x_{i_k}\} $ with $ i_1 < i_2 < \dots < i_k $, and a path starting at $ 0 $, visiting these positions in order, with total travel time $ \leq t $, where travel time between positions $ a $ and $ b $ is $ |a - b| $.
Equivalently, maximize $ k $ such that there exist indices $ l \leq r $ with $ r - l + 1 = k $, and the minimal time to collect all bonuses in $ \{x_l, x_{l+1}, \dots, x_r\} $ is $ \leq t $, where the minimal time for interval $ [l, r] $ is:
$$
\min\left( 2 \cdot |x_l| + |x_r - x_l|,\ 2 \cdot |x_r| + |x_r - x_l| \right)
$$
if $ x_l \leq 0 \leq x_r $, or
$$
\min\left( |x_l| + |x_r| \right) \quad \text{if both } x_l, x_r \leq 0 \text{ or both } \geq 0
$$
More precisely, for a contiguous segment $ [l, r] $:
- If $ x_r \leq 0 $: time = $ |x_l| $
- If $ x_l \geq 0 $: time = $ x_r $
- If $ x_l < 0 < x_r $: time = $ 2 \cdot \min(|x_l|, x_r) + (x_r - x_l) $
Thus, define for each contiguous subarray $ [l, r] $:
$$
T(l, r) =
\begin{cases}
|x_l| & \text{if } x_r \leq 0 \\
x_r & \text{if } x_l \geq 0 \\
2 \cdot \min(|x_l|, x_r) + (x_r - x_l) & \text{if } x_l < 0 < x_r
\end{cases}
$$
Maximize $ r - l + 1 $ subject to $ T(l, r) \leq t $.