Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

$$$ (a_1 + a_2) ⊕ (a_1 + a_3) ⊕ … ⊕ (a_1 + a_n) \\\ ⊕ (a_2 + a_3) ⊕ … ⊕ (a_2 + a_n) \\\ … \\\ ⊕ (a_{n-1} + a_n) \\\ $$$

Here x ⊕ y is a bitwise XOR operation (i.e. x ^ y in many modern programming languages). You can read about it in Wikipedia: <https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation>.

Input

The first line contains a single integer n (2 ≤ n ≤ 400 000) — the number of integers in the array.

The second line contains integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^7).

Output

Print a single integer — xor of all pairwise sums of integers in the given array.

Examples

Input


2
1 2


Output


3

Input


3
1 2 3


Output


2

Note

In the first sample case there is only one sum 1 + 2 = 3.

In the second sample case there are three sums: 1 + 2 = 3, 1 + 3 = 4, 2 + 3 = 5. In binary they are represented as 011_2 ⊕ 100_2 ⊕ 101_2 = 010_2, thus the answer is 2.

⊕ is the bitwise xor operation. To define x ⊕ y, consider binary representations of integers x and y. We put the i-th bit of the result to be 1 when exactly one of the i-th bits of x and y is 1. Otherwise, the i-th bit of the result is put to be 0. For example, 0101_2   ⊕   0011_2 = 0110_2.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class C1322B_2 {

    public static void main(String[] args) {
        MyScanner scanner = new MyScanner();
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
//        int n = (int) 1e4;
//        int[] a = new int[n];
//        for (int i = 0; i < n; i++) {
//            a[i] = (int) (Math.random() * 1e7) + 1;
////            a[i] = 11 * (i / 3);
//        }

//        int refAns = 0;
//        for (int i = 0; i < n; i++) {
//            for (int j = i + 1; j < n; j++) {
//                refAns ^= a[i] + a[j];
//            }
//        }
//        System.out.println("refAns: " + refAns);

        // 计算第digit二进制位是1还是0
        int binaryLenLimit = 25; // 2*1e7是25位2进制
        int ans = 0;
        int[] order = new int[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        int[] lowParts = new int[n];

        // 对每个二进制位，看看是1还是0。
        // 因为是抑或操作，所以这一位1的个数是奇数，则结果是1，否则是0。
        for (int digit = 0; digit < binaryLenLimit; digit++) {
            int bitMask = 1 << digit;
            int acc = 0;

            // 原来的order是有序的，添加了digit这一位之后，需要重新排序。
            // 但是只需要按照digit这一位是0放到是1的前面即可，digit这一位相等的按照原来的顺序不变，即可保证还是从小到大的。
            List<Integer> order0 = new ArrayList<>();
            List<Integer> order1 = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((a[order[i]] & (1 << digit)) == 0) {
                    order0.add(order[i]);
                } else {
                    order1.add(order[i]);
                }
            }

            int size0 = order0.size();
            System.arraycopy(order0.stream().mapToInt(i -> i).toArray(), 0, order, 0, size0);
            System.arraycopy(order1.stream().mapToInt(i -> i).toArray(), 0, order, size0, order1.size());
            int lowPartMask = (1 << digit) - 1;
            for (int i = 0; i < order.length; i++) {
                lowParts[i] = a[order[i]] & lowPartMask;
            }

            int p00 = size0;
            for (int i = 0; i < size0; i++) {
                while (p00 > 0 && lowParts[i] + lowParts[p00 - 1] >= bitMask) {
                    p00--;
                }
                int count = size0 - Math.max(p00, i + 1);
//                System.out.println(String.format("digit=%d,00,%d种方案", digit, count));
                acc = (acc + count) & 1;
            }

            int p01 = n - 1;
            for (int i = 0; i < size0; i++) {
                while (p01 >= size0 && lowParts[i] + lowParts[p01] >= bitMask) {
                    p01--;
                }
                int count = p01 - size0 + 1;
//                System.out.println(String.format("digit=%d,01,%d种方案", digit, count));
                acc = (acc + count) & 1;
            }

            int p11 = n;
            for (int i = size0; i < n; i++) {
                while (p11 > size0 && lowParts[i] + lowParts[p11 - 1] >= bitMask) {
                    p11--;
                }
                int count = n - Math.max(p11, i + 1);
//                System.out.println(String.format("digit=%d,11,%d种方案", digit, count));
                acc = (acc + count) & 1;
            }

            ans += acc << digit;
        }

        System.out.println(ans);
    }

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }

}
