People in the Tomskaya region like magic formulas very much. You can see some of them below. Imagine you are given a sequence of positive integer numbers p 1 , p 2 , ..., p n . Lets write down some magic formulas: Here, "mod" means the operation of taking the residue after dividing. The expression means applying the bitwise xor (excluding "OR") operation to integers x and y . The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by "^", in Pascal — by "xor". People in the Tomskaya region like magic formulas very much, but they don't like to calculate them! Therefore you are given the sequence p , calculate the value of Q .

输入描述:

The first line of the input contains the only integer n (1 ≤ n ≤ 106). The next line contains n integers: p1, p2, ..., pn (0 ≤ pi ≤ 2·109).

输出描述:

The only line of output should contain a single integer — the value of Q.