配点 : 1300 点
問題文
Niwango,dwango 员工, N 我正在制作一个步骤金字塔。 每个 关于上面的 1 \leq i \leq N 关于,从上面 i 步骤是 2i - 1 块水平排列。 此外,当查看每行中央的块时,它们是垂直排列的。 例如 4 在分层金字塔的情况下,它将如下图所示。
二王后君很长 2N-1 序列 我决定使用 a 将一个整数写入金字塔的每个块中。 二王后君分别是 关于 1 \leq i \leq 2N-1 关于 N 从该行的左侧开始 块中的整数 i 写入 a_i 后,我将值写入其他块,以便满足以下条件。
- 每个块中写入的整数分别是左下、正下和右下块中写入的整数。 x, y, z 作为 x xor y xor z 变为 只有一个
- 但是,xor 表示按位异或
1 查找第一行块中写入的整数。
但是,N 可以非常大 仅 a 以以下格式给出:详细信息请参阅示例 另请参见 1 。
- 整数 M 和长度 M 序列 我决定使用 v,L 被给予
- 这是 重复a 被给予 v_1 被 L_{1} 次的数字序列, 序列重复v_2 被 L_{2} 次,..., 表示将按此顺序重复v_M 被 L_{M} 次的数字序列串联而成的序列。 大于或等于
制約
- 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