题目描述

高橋君と青木君が、いくつかの石からなる $N$ 個の山を用いて石とりゲームで対戦します。

はじめ、$i\ =\ 1,\ 2,\ \ldots,\ N$ について、$i$ 番目の山は $A_i$ 個の石からなります。 高橋君からはじめ、$2$ 人は交互に次の行動をくりかえします。

石が $1$ 個以上残っている山を $1$ つ選び、その山から $1$ 個以上の石を取り除く。

ただし、このゲームには $M$ 種類の禁じ手があり、禁じ手に該当する行動を行うことはできません。
$i\ =\ 1,\ 2,\ \ldots,\ M$ について、$i$ 種類目の禁じ手は「ちょうど $X_i$ 個の石からなる山からちょうど $Y_i$ 個の石を取り除くこと」です。

先に行動を行うことができなくなった方のプレイヤーの負けとなり、負けなかった方のプレイヤーの勝ちとなります。 両者が自身が勝つために最適な戦略をとるとき、どちらのプレイヤーが勝つかを答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出格式

両者が自身が勝つために最適な戦略をとるとき、高橋君が勝つならば Takahashi と、青木君が勝つならば Aoki と出力せよ。

题目大意

$n$堆石子的nim游戏,有$m$个限制,第$i$个限制$x_i,y_i$表示若一个石子堆剩余石子为$x_i$,你就不能从其中拿走$y_i$个.问先手必胜/必负.

$n,m\le 2\times 10^5,a_i\le 10^{18}$

3 4
1 2 4
2 1
3 3
3 1
1 1

Takahashi

1 5
5
5 1
5 2
5 3
5 4
5 5

Aoki

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ M\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^{18}$
• $1\ \leq\ Y_i\ \leq\ X_i\ \leq\ 10^{18}$
• $ i\ \neq\ j\ \Rightarrow\ (X_i,\ Y_i)\ \neq\ (X_j,\ Y_j) $
• 入力はすべて整数

Sample Explanation 1

$i\ =\ 1,\ 2,\ 3$ について、$i$ 番目の山にある石の個数を $A'_i$ とし、 それぞれの山にある石の個数を数列 $A'\ =\ (A'_1,\ A'_2,\ A'_3)$ を用いて表すことにします。 ゲームが始まる前の時点では、$A'\ =\ (1,\ 2,\ 4)$ です。ゲームの進行の一例として次のものがあります。 - まず、高橋君が $3$ 番目の山から石を $1$ 個取り除く。その結果、$A'\ =\ (1,\ 2,\ 3)$ となる。 - 次に、青木君が $2$ 番目の山から石を $2$ 個取り除く。その結果、$A'\ =\ (1,\ 0,\ 3)$ となる。 - さらに、高橋君が $3$ 番目の山から石を $2$ 個取り除く。その結果、$A'\ =\ (1,\ 0,\ 1)$ となる。 その後の時点で、$1$ 番目と $3$ 番目の山にはまだ石が $1$ 個ずつ残っていますが、ちょうど $1$ 個の石からなる山からちょうど $1$ 個の石を取り除くことは $4$ 種類目の禁じ手に該当するため、青木君は行動を行うことができません。したがって、高橋君の勝ちとなります。