問題文

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 以上の奇数
• 与えられる入力は全て整数

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