配点 : $600$ 点

問題文

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

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

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

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

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

制約

• $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)$
• 入力はすべて整数

入力

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

$N$ $M$

$A_1$ $A_2$ $\ldots$ $A_N$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_M$ $Y_M$

出力

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

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

Takahashi

$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$ 種類目の禁じ手に該当するため、青木君は行動を行うことができません。したがって、高橋君の勝ちとなります。

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

Aoki