← 返回题目列表

AtCoder · dwacon2018_final_c

C. 异或金字塔

中文机器翻译题面 查看原题

配点 : 1300 点

問題文

Niwango,dwango 员工, N 我正在制作一个步骤金字塔。 每个 关于上面的 1 \leq i \leq N 关于,从上面 i 步骤是 2i - 1 块水平排列。 此外,当查看每行中央的块时,它们是垂直排列的。 例如 4 在分层金字塔的情况下,它将如下图所示。

86ebefd7e8326c213b1a62b50322a905.png

二王后君很长 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 。
ca0b3d434a1e0d28287d47e1ecfbb11d.png

入力例 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