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.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class CFD {
    private static boolean isLocalEnv = false;
    public static void main(String[] args) throws FileNotFoundException, InterruptedException {
        InputStream stream = System.in;
        Logger logger = new Logger();
        if (args.length>1 && args[0].equals("LOCAL") && args[1].equals("YES")) {
            isLocalEnv = true;
            File inputFile = new File("resources/input.in");
            stream = new DataInputStream(new FileInputStream(inputFile));
            logger.enableLogging(true, "resources/logs.txt");
        }
        InputReader in = new InputReader(stream);
        PrintWriter out = new PrintWriter(System.out);
        Thread th = new Thread(null, () -> new Task1().solve(in, out, logger), "Task1", 1 << 24);
        th.start();
        th.join();
        out.close();
        logger.close();
    }

    static class Task1 {
        int maxBits = 27;

        void solve(InputReader in, PrintWriter out, Logger logger) {
            int n = in.nextInt();
            int[] a = new int[n];

            for(int i=0; i<n; i++) {
                a[i] = in.nextInt();
            }
            if(isLocalEnv) logger.logln("Answer: "+bruteforce(a));

            long ans = 0;
            for (int bit=0; bit<maxBits; bit++) {
                if (bitKInFinalAns(a, bit) %2 == 1) {
                    ans += (1<<bit);
                }
            }
            out.println(ans);
        }

        long bitKInFinalAns(int[] a, int k) {
            int[] b = Arrays.stream(a).map(x -> x%(1<<(k+1))).sorted().toArray();
            long count = 0;

            for (int i=0; i<b.length; i++) {
                int curr = b[i];

                // 2^k to 2^(k+1)-1
                int start = lowerBound(b, i+1, (1 << k) - curr);
                int end = lowerBound(b, i+1, (1 << k + 1) - curr);
                if (end >= start) count += (end - start);

                // 2^(k+1)+2^k to 2^(k+2)-2
                start = lowerBound(b, i+1, (1 << k + 1) + (1 << k) - curr);
                end = lowerBound(b, i+1, (1 << k + 2) - 1 - curr);
                if (end >= start) count += (end - start);
            }

            return count;
        }

        int lowerBound(int[] a, int lo, int key) { // first element not less than key
            int hi=a.length-1;
            while(hi>=lo) {
                int mid = (lo+hi)>>1;
                if(a[mid] < key) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            return lo;
        }

        int upperBound(int[] a, int key) { // first element greater than key
            int lo=0, hi=a.length-1;
            while(hi>=lo) {
                int mid = (lo+hi)>>1;
                if(a[mid] <= key) {
                    lo = mid+1;
                } else {
                    hi = mid-1;
                }
            }
            return lo;
        }

        long bruteforce(int[] a) {
            int n = a.length;
            long result = 0;
            for(int i=0; i<n; i++) {
                for(int j=i+1; j<n; j++) {
                    result = result^(a[i]+a[j]);
                }
            }
            return result;
        }

        long fastPow(long a, long b) {
            if (a==0) return 0;
            long result = 1;
            while(b > 0) {
                if ((b&1) == 1){ result *= a; }
                a *= a;
                b >>= 1;
            }
            return result;
        }
    }

    static class Logger {
        private PrintWriter logger;
        private boolean loggingEnabled;

        void enableLogging(boolean enable, String filename) {
            this.loggingEnabled = enable;
            try {
                if (loggingEnabled) this.logger = new PrintWriter(filename);
            } catch (FileNotFoundException ignored) {
            }
        }

        void log(Object s) {
            if (loggingEnabled) {
                logger.print(s.toString());
            }
        }

        void logln(Object s) {
            if (loggingEnabled) {
                logger.println(s.toString());
            }
        }

        void close() {
            if (loggingEnabled) logger.close();
        }
    }

    static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, numChars;
        private SpaceCharFilter filter;

        InputReader(InputStream stream) {
            this.stream = stream;
        }

        int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        interface SpaceCharFilter {
            boolean isSpaceChar(int ch);
        }
    }
}
