問題文
高橋君と青木君が、いくつかの石からなる N 個の山を用いて石とりゲームで対戦します。
はじめ、i=1,2,ldots,N について、i 番目の山は Ai 個の石からなります。 高橋君からはじめ、2 人は交互に次の行動をくりかえします。
石が 1 個以上残っている山を 1 つ選び、その山から 1 個以上の石を取り除く。
ただし、このゲームには M 種類の禁じ手があり、禁じ手に該当する行動を行うことはできません。
i=1,2,ldots,M について、i 種類目の禁じ手は「ちょうど Xi 個の石からなる山からちょうど Yi 個の石を取り除くこと」です。
先に行動を行うことができなくなった方のプレイヤーの負けとなり、負けなかった方のプレイヤーの勝ちとなります。 両者が自身が勝つために最適な戦略をとるとき、どちらのプレイヤーが勝つかを答えてください。
制約
- 1leqNleq2times105
- 1leqMleq2times105
- 1leqAileq1018
- 1leqYileqXileq1018
- ineqjRightarrow(Xi,Yi)neq(Xj,Yj)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A1 A2 ldots AN
X1 Y1
X2 Y2
vdots
XM YM
出力
両者が自身が勝つために最適な戦略をとるとき、高橋君が勝つならば Takahashi
と、青木君が勝つならば Aoki
と出力せよ。
入力例 1
出力例 1
i=1,2,3 について、i 番目の山にある石の個数を Ai′ とし、 それぞれの山にある石の個数を数列 A′=(A1′,A2′,A3′) を用いて表すことにします。
ゲームが始まる前の時点では、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 種類目の禁じ手に該当するため、青木君は行動を行うことができません。したがって、高橋君の勝ちとなります。
入力例 2
出力例 2