AT_abc255_g [ABC255G] Constrained Nim

[problemUrl]: https://atcoder.jp/contests/abc255/tasks/abc255_g 高橋君と青木君が、いくつかの石からなる $ 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` と出力せよ。

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