题目描述

マス $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 を出力せよ。

题目大意

Takahashi 和 Aoki 在一个长为 $N$ 的数轴上做游戏。初始时，有 $M$ 个点有颜色，$X_i$ 位置上有颜色为 $Y_i$ 的点。Takahashi 先手，两人轮流操作，操作的内容是在数轴上没有点的位置上放置一点，需要满足其颜色与相邻两点（如果不为空）的颜色不同。若轮到一人操作时，无法再进行操作，则另一人获胜，游戏结束。给出游戏初始局面（保证合法），问谁有必胜策略。

$N\le 10^{18},M\le\min(N,2\times10^5)$

7 2
2 0
4 1

Takahashi

3 3
1 1
2 0
3 1

Aoki

1000000000000000000 0

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$ が書きこまれているため、先手の高橋君は行動できず青木君の勝ちとなります。