问题描述

dwango公司的员工Niwan-Go君正在制作一个N层的金字塔。对于每一个$1 \leq i \leq N$，第$i$层从上往下有$2i - 1$个方块排列成一行。而且，在每层的中心格子上，这些数字是竖直排列的。例如，对于一个4层的金字塔，如下图所示：

Niwan-Go君使用长度为$2N-1$的整数序列$a$来给金字塔的每一个方块写入一个整数。Niwan-Go君先给第$N$层的第$i$个方块写入整数$a_i$，然后在其余方块中按照以下条件写入数值：

• 每个方块的数值是左下方块、正下方块和右下方块的数值的异或和，即$x \oplus y \oplus z$。
• 这里，$\oplus$表示按位异或。

请计算第$1$层的方块上写有的整数。

注意，$N$的值可能非常大，因此只给出$a$的形式如下所示。详细说明请参见示例$1$。

约束条件

• $1 \leq M \leq 252{,}525$
• $0 \leq v_i \leq 10^9$
• $1 \leq L_i \leq 10^9$
• ${\rm Σ}{L_i}$ 是大于等于3的奇数
• 所有给出的输入都是整数

输入

从标准输入读取数据，数据格式如下：

$M$ $v_1$ $L_1$ $:$ $v_{M}$ $L_{M}$

输出

输出答案。

输入示例 1

4
1 1
2 3
3 2
4 1

输出示例 1

6

• 数列$a$是由顺序拼接的$(1), (2,2,2), (3,3), (4)$得到的，即$(1,2,2,2,3,3,4)$。
• 这个时候，形成的金字塔如下图所示，第$1$层的方块上写有数字$6$。

输入示例 2

1
1 999999999

输出示例 2

1

• 当$N=499999999$时，数列$a$由$1$重复$999999999$次得到。第$1$层的方块上写有数字$1$。

输入示例 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

输出示例 3

590313667