Problem Description

Niwango, an employee of dwango, is working on creating a pyramid with $ N $ levels. For each $1 \leq i \leq N$, the $ i $-th level from the top consists of $ 2i - 1 $ blocks arranged in a single row. Additionally, when focusing on the central block of each level, they are aligned in a single column. For example, a pyramid with 4 levels looks like the following diagram:

Niwango decided to use a sequence of length $ 2N-1 $, $ a $, to write integers into each block of the pyramid. For each $1 \leq i \leq 2N-1$, Niwango wrote the integer $ a_i $ into the $ i $-th block from the left on the $ N $-th level. Then, he filled in the other blocks according to the following rule:

• Each block contains the integer which is the bitwise XOR of the integers written in the blocks directly below it (left, center, right).

Determine the integer written in the block on the 1st level.

Since $ N $ can be very large, only $ a $ is given in the following format. Refer to Sample 1 for more details.

• An integer $ M $ and a sequence of length $ M $, $ v, L $, are given.
• This indicates that $ a $ is obtained by concatenating the sequences where $ v_1 $ is repeated $ L_1 $ times, $ v_2 $ is repeated $ L_2 $ times, ..., $ v_M $ is repeated $ L_M $ times, in this order.

Input Format

The input is given from the standard input in the following format:

$ M $ $ v_1 $ $ L_1 $ $ : $ $ v_M $ $ L_M $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

4
1 1
2 3
3 2
4 1

Sample Output #1

6

Sample Input #2

1
1 999999999

Sample Output #2

1

Sample Input #3

21
89 54
6724143 9
122809 50
217 28
11179392 38
756 6
127 53
7490953 33
7235 47
877957251 1
708258674 49
539545 3
20170110 6
6991539 40
4 14
3 21
204 35
9 3
680 41
158030498 44
34248 10

Sample Output #3

590313667

Notes/Hints

Constraints

• $1 \leq M \leq 252,525$
• $0 \leq v_i \leq 10^9$
• $1 \leq L_i \leq 10^9$
• $\Sigma L_i$ is an odd number greater than or equal to 3
• All given inputs are integers

Sample Explanation 1

• $ a $ is the sequence obtained by concatenating $ (1), (2,2,2), (3,3), (4) $ in this order, resulting in $ (1,2,2,2,3,3,4) $. The pyramid obtained from this sequence has the integer 6 written in the block on the 1st level, as shown in the following diagram:

Sample Explanation 2

• With $ N=499999999 $, $ a $ is a sequence where 1 is repeated 999999999 times. The integer written in the block on the 1st level is 1.

见题面 Input 部分

见题面 Output 部分