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 p1, p2, ..., pn. Lets write down some magic formulas:

<image><image>

Here, "mod" means the operation of taking the residue after dividing.

The expression <image> 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.

Input

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).

Output

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

Examples

Input

3
1 2 3


Output

3
#include <bits/stdc++.h>
using namespace std;
bool PIIfs(const pair<int, int>& a, const pair<int, int>& b) {
  return a.first < b.first || (a.first == b.first && a.second < b.second);
}
bool PIIsf(const pair<int, int>& a, const pair<int, int>& b) {
  return a.second < b.second || (a.second == b.second && a.first < b.first);
}
bool PIIFS(const pair<int, int>& a, const pair<int, int>& b) {
  return a.first > b.first || (a.first == b.first && a.second > b.second);
}
bool PIISF(const pair<int, int>& a, const pair<int, int>& b) {
  return a.second > b.second || (a.second == b.second && a.first > b.first);
}
bool PIIfS(const pair<int, int>& a, const pair<int, int>& b) {
  return a.first < b.first || (a.first == b.first && a.second > b.second);
}
bool PIIsF(const pair<int, int>& a, const pair<int, int>& b) {
  return a.second < b.second || (a.second == b.second && a.first > b.first);
}
bool PIIFs(const pair<int, int>& a, const pair<int, int>& b) {
  return a.first > b.first || (a.first == b.first && a.second < b.second);
}
bool PIISf(const pair<int, int>& a, const pair<int, int>& b) {
  return a.second > b.second || (a.second == b.second && a.first < b.first);
}
template <typename T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <typename T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b, c), d);
}
template <typename T>
inline T max(T a, T b, T c, T d, T e) {
  return max(max(a, b, c, d), e);
}
template <typename T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <typename T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b, c), d);
}
template <typename T>
inline T min(T a, T b, T c, T d, T e) {
  return min(min(a, b, c, d), e);
}
template <typename T>
inline istream& RD(T& x) {
  return cin >> x;
}
template <typename T, typename U>
inline istream& RD(T& a, U& b) {
  return cin >> a >> b;
}
template <typename T, typename U, typename V>
inline istream& RD(T& a, U& b, V& c) {
  return cin >> a >> b >> c;
}
template <typename T, typename U, typename V, typename W>
inline istream& RD(T& a, U& b, V& c, W& d) {
  return cin >> a >> b >> c >> d;
}
template <typename T, typename U, typename V, typename W, typename X>
inline istream& RD(T& a, U& b, V& c, W& d, X& e) {
  return cin >> a >> b >> c >> d >> e;
}
template <typename T>
void checkmin(T& a, const T& b) {
  if (b < a) a = b;
}
template <typename T>
void checkmax(T& a, const T& b) {
  if (b > a) a = b;
}
const int maxn = 1000100;
int VAL[2 * maxn];
int INPUT[maxn];
int L[2 * maxn];
int R[2 * maxn];
int MARK[2 * maxn];
inline void mergeMark(int& son, const int& father) { son += father; }
inline void setMark(int& where, const int& what) { where = what; }
inline int mergeValVal(const int& a, const int& b) { return a + b; }
inline const int withValue(const int& mark, const int& val, int l, int r) {
  return val + (r - l) * mark;
}
inline void clearMark(int& m) { m = 0; }
const bool MERGABLE = true;
class SegmentTree {
 public:
  SegmentTree(size_t N) : query_head(indexof(0, N)) {
    memset(MARK, 0, sizeof(MARK));
    build(0, N);
  }
  int query(int l, int r) { return query_aid(query_head, l, r); }
  void update(int l, int r, const int& mark) {
    update_aid(query_head, l, r, mark);
  }

 private:
  const int query_head;
  inline int indexof(int l, int r) {
    return (l - 1 + r) - ((r - l == 1) ? 0 : ((l + r) & 1));
  }
  void build(int l, int r) {
    int ind = indexof(l, r);
    if (l + 1 < r) {
      build(l, (l + r) >> 1);
      build((l + r) >> 1, r);
      L[ind] = l;
      R[ind] = r;
      VAL[ind] = mergeValVal(VAL[indexof(l, (l + r) / 2)],
                             VAL[indexof((l + r) / 2, r)]);
    } else {
      L[ind] = l;
      R[ind] = r;
      VAL[ind] = INPUT[l];
    }
  }
  void pushDown(int which_node) {
    const int& mark = MARK[which_node];
    if (mark) {
      int l = L[which_node];
      int r = R[which_node];
      if (r - l > 1) {
        if (MERGABLE) {
          mergeMark(MARK[indexof(l, (l + r) / 2)], (mark));
          mergeMark(MARK[indexof((l + r) / 2, r)], (mark));
        } else {
          pushDown(indexof(l, (l + r) / 2));
          pushDown(indexof((l + r) / 2, r));
          setMark(MARK[indexof(l, (l + r) / 2)], (mark));
          setMark(MARK[indexof((l + r) / 2, r)], (mark));
        }
      }
      VAL[which_node] = withValue(mark, VAL[which_node], l, r);
      clearMark(MARK[which_node]);
    }
  }
  int query_aid(int which_node, int l, int r) {
    pushDown(which_node);
    int lbound = L[which_node];
    int rbound = R[which_node];
    if (l <= lbound && rbound <= r) {
      return VAL[which_node];
    } else {
      int ans;
      int mid = (lbound + rbound) >> 1;
      if (l < mid) {
        ans = query_aid(indexof(lbound, mid), l, r);
        if (r > mid) {
          ans = mergeValVal(ans, query_aid(indexof(mid, rbound), l, r));
        }
      } else {
        ans = query_aid(indexof(mid, rbound), l, r);
      }
      return ans;
    }
  }
  void update_aid(int which_node, int l, int r, const int& mark) {
    int lbound = L[which_node];
    int rbound = R[which_node];
    if (l <= lbound && rbound <= r) {
      if (MERGABLE) {
        mergeMark(MARK[which_node], (mark));
      } else {
        pushDown(which_node);
        mergeMark(MARK[which_node], (mark));
      }
    } else {
      pushDown(which_node);
      int mid = (lbound + rbound) / 2;
      if (l < mid) {
        update_aid(indexof(lbound, mid), l, r, mark);
        if (r > mid) {
          update_aid(indexof(mid, rbound), l, r, mark);
        }
      } else {
        update_aid(indexof(mid, rbound), l, r, mark);
      }
      pushDown(indexof(lbound, mid));
      pushDown(indexof(mid, rbound));
      VAL[which_node] =
          mergeValVal(VAL[indexof(lbound, mid)], VAL[indexof(mid, rbound)]);
    }
  }
};
int dodo(int n) {
  int ans = 0;
  memset(INPUT, 0, sizeof(INPUT));
  SegmentTree st(n + 1);
  for (int i = 2; i <= n; i++) {
    int bv = n / i;
    int rm = n % i;
    st.update(0, i, bv);
    if (rm > 0) st.update(0, rm + 1, 1);
  }
  for (int i = 1; i <= (int)(n); ++i) {
    int q = st.query(i, i + 1);
    if (q % 2 == 1) {
      ans ^= i;
    }
  }
  return ans;
}
int main() {
  std::ios::sync_with_stdio(false);
  int n;
  int ans = 0;
  RD(n);
  for (int i = 0; i < (int)(n); ++i) {
    int x;
    RD(x);
    ans ^= x;
  }
  ans ^= dodo(n);
  cout << ans << '\n';
  return 0;
}
