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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.util.Random;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Rustam Musin (t.me/musin_acm)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    BPodarok solver = new BPodarok();
    solver.solve(1, in, out);
    out.close();
  }

  static class BPodarok {
    Random rnd = new Random(239);

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      if (false) {
        test3();
      }
      int n = in.readInt();
      int[] a = in.readIntArray(n);
//    out.print(naive(a));
      out.print(newSolve(a));
    }

    int newSolve(int[] a) {
      int res = 0;
      for (int b = 0; b < 30; b++) {
        if (newSolve(a, b) % 2 == 1) {
          res |= 1 << b;
        }
      }
      return res;
    }

    long newSolve(int[] a, int bit) {
      int[] b = new int[a.length];
      for (int i = 0; i < a.length; i++) {
        b[i] = a[i] % (1 << (bit + 1));
      }
      Arrays.sort(b);
      int L1 = 1 << bit;
      int R1 = (L1 << 1) - 1;
      int L2 = (L1 << 1) | L1;
      int R2 = (L1 << 1) | R1;
      long count = 0;
      for (int x : b) {
        count += getCount(b, L1 - x, R1 - x);
        count += getCount(b, L2 - x, R2 - x);
        if (inside(L1 - x, R1 - x, x)) {
          count--;
        }
        if (inside(L2 - x, R2 - x, x)) {
          count--;
        }
      }
      return count >> 1;
    }

    boolean inside(int l, int r, int x) {
      return l <= x && x <= r;
    }

    int getCount(int[] a, int l, int r) {
      return getCount(a, r) - getCount(a, l - 1);
    }

    int getCount(int[] a, int x) {
      int l = -1;
      int r = a.length;
      while (r - l > 1) {
        int m = l + r >> 1;
        if (a[m] <= x) {
          l = m;
        } else {
          r = m;
        }
      }
      return l;
    }

    int naive(int[] a) {
      int res = 0;
      for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
          res ^= a[i] + a[j];
        }
      }
      return res;
    }

    void test3() {
      for (int t = 0; ; t++) {
        int n = 10;
        int m = 5;
        int[] a = genArray(n, m);
        int naive = naive(a);
        int sol = newSolve(a);
        if (naive != sol) {
          System.err.println("FF");
          naive = naive(a);
          sol = newSolve(a);
        }
      }
    }

    int[] genArray(int n, int m) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++) {
        a[i] = rnd.nextInt(m);
      }
      return a;
    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
      writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void close() {
      writer.close();
    }

    public void print(int i) {
      writer.print(i);
    }

  }

  static class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private InputReader.SpaceCharFilter filter;

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

    public int[] readIntArray(int size) {
      int[] array = new int[size];
      for (int i = 0; i < size; i++) {
        array[i] = readInt();
      }
      return array;
    }

    public 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++];
    }

    public int readInt() {
      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;
    }

    public boolean isSpaceChar(int c) {
      if (filter != null) {
        return filter.isSpaceChar(c);
      }
      return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

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

    }

  }
}

