Richard wants to demonstrate that there are things far worse than Fenwick in terms of things to remember, and the first example he gave was heap Dijkstra.

To demonstrate this, he wants a problem that has many edges, but doesn't benefit too much from fast I/O. So a natural candidate is https://szkopul.edu.pl/problemset/problem/ROXsaseQWYR11jbNvCgM19Er/site/?key=statement.

The algorithm in that problem is basically to construct a graph on the modulus against ~a_1~, and then do shortest path to look for the smallest number in each modulus that could be constructed.

Your job will be to solve this problem with some tuned bounds.

Input Specification

The first line contains a single integer, ~N~.

~N~ lines follow, each containing a single integer ~a_i~.

You may assume ~N \le 100~ and that ~1 \le a_i \le 2^{40}~.

Furthermore, ~a_1 \le 10^5~.

Output Specification

Let ~x_i~ be the smallest value that can be attained that is the sum of some multiset of ~a_i~ values that is equivalent to ~i \pmod{a_1}~. Print the XOR of all ~x_i~ for ~0 \le i < a_1~.

It is guaranteed that ~x_i~ is well-defined.

Sample Input

6
10
1
11
22
33
478154081019

Sample Output

1