AT_arc151_c [ARC151C] 01 Game

[problemUrl]: https://atcoder.jp/contests/arc151/tasks/arc151_c マス $ 1 $ 、マス $ 2 $ 、$ \ldots $ 、マス $ N $ の $ N $ 個のマスがあり、 $ i\ =\ 1,\ 2,\ \ldots,\ N-1 $ についてマス $ i $ とマス $ i+1 $ は隣り合っています。 はじめ、$ M $ 個のマスには $ 0 $ または $ 1 $ が書かれています。 具体的には、$ i\ =\ 1,\ 2,\ \ldots,\ M $ について、マス $ X_i $ に $ Y_i $ が書かれています。 また、その他の $ N-M $ 個のマスには何も書かれていません。 高橋君と青木君が $ 2 $ 人で対戦ゲームをします。 高橋君の先手で、$ 2 $ 人は交互に下記の行動を行います。 - まだ何も書かれていないマスを $ 1 $ つ選び、そのマスに $ 0 $ または $ 1 $ を書きこむ。 ただしその結果、ある $ 2 $ つの隣り合うマスに同じ数字が書かれた状態になってはならない。 先に行動することができなくなったプレイヤーの負けとなり、負けなかったプレイヤーの勝ちとなります。 両者がそれぞれ自身が勝つために最適な戦略をとる場合に、どちらが勝つかを判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_M $ $ Y_M $

高橋君が勝つ場合は `Takahashi` を、青木君が勝つ場合は `Aoki` を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^{18} $ - $ 0\ \leq\ M\ \leq\ \min\lbrace\ N,\ 2\ \times\ 10^5\ \rbrace $ - $ 1\ \leq\ X_1\ \lt\ X_2\ \lt\ \cdots\ \lt\ X_M\ \leq\ N $ - $ Y_i\ \in\ \lbrace\ 0,\ 1\rbrace $ - $ X_i\ +\ 1\ =\ X_{i+1}\ \implies\ Y_i\ \neq\ Y_{i+1} $ - 入力はすべて整数 ### Sample Explanation 1 ゲームの進行の一例を示します。 1. 高橋君がマス $ 6 $ に $ 0 $ を書きこむ。 2. 青木君がマス $ 1 $ に $ 1 $ を書きこむ。 3. 高橋君がマス $ 7 $ に $ 1 $ を書きこむ。 その後、青木君はどのマスにも $ 0 $ または $ 1 $ を書きこむことが出来ないため、高橋君の勝ちとなります。 ### Sample Explanation 2 ゲーム開始時点ですでにすべてのマスに $ 0 $ または $ 1 $ が書きこまれているため、先手の高橋君は行動できず青木君の勝ちとなります。