/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
マス 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 つの隣り合うマスに同じ数字が書かれた状態になってはならない。
先に行動することができなくなったプレイヤーの負けとなり、負けなかったプレイヤーの勝ちとなります。
両者がそれぞれ自身が勝つために最適な戦略をとる場合に、どちらが勝つかを判定してください。
制約
- 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}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 Y_1 X_2 Y_2 \vdots X_M Y_M
出力
高橋君が勝つ場合は Takahashi を、青木君が勝つ場合は Aoki を出力せよ。
入力例 1
7 2 2 0 4 1
出力例 1
Takahashi
ゲームの進行の一例を示します。
- 高橋君がマス 6 に 0 を書きこむ。
- 青木君がマス 1 に 1 を書きこむ。
- 高橋君がマス 7 に 1 を書きこむ。
その後、青木君はどのマスにも 0 または 1 を書きこむことが出来ないため、高橋君の勝ちとなります。
入力例 2
3 3 1 1 2 0 3 1
出力例 2
Aoki
ゲーム開始時点ですでにすべてのマスに 0 または 1 が書きこまれているため、先手の高橋君は行動できず青木君の勝ちとなります。
入力例 3
1000000000000000000 0
出力例 3
Aoki
Score : 600 points
Problem Statement
There are N squares called square 1, square 2, \ldots, square N, where square i and square i+1 are adjacent for each i = 1, 2, \ldots, N-1.
Initially, M of the squares have 0 or 1 written on them. Specifically, for each i = 1, 2, \ldots, M, Y_i is written on square X_i. The other N-M squares have nothing written on them.
Takahashi and Aoki will play a game against each other. The two will alternately act as follows, with Takahashi going first.
- Choose a square with nothing written yet, and write 0 or 1 on that square. Here, it is forbidden to make two adjacent squares have the same digit written on them.
The first player to be unable to act loses; the other player wins.
Determine the winner when both players adopt the optimal strategy for their own victory.
Constraints
- 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}
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M X_1 Y_1 X_2 Y_2 \vdots X_M Y_M
Output
If Takahashi wins, print Takahashi; if Aoki wins, print Aoki.
Sample Input 1
7 2 2 0 4 1
Sample Output 1
Takahashi
Here is one possible progression of the game.
- Takahashi writes 0 on square 6.
- Aoki writes 1 on square 1.
- Takahashi writes 1 on square 7.
Then, Aoki cannot write 0 or 1 on any square, so Takahashi wins.
Sample Input 2
3 3 1 1 2 0 3 1
Sample Output 2
Aoki
Since every square already has 0 or 1 written at the beginning, Takahashi, who goes first, cannot act, so Aoki wins.
Sample Input 3
1000000000000000000 0
Sample Output 3
Aoki