/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
高橋君と青木君が以下のようなゲームをします。
- i=1,2,\ldots,N の順に次の操作をする。
- l_i 以上 r_i 以下の整数を 1 個ずつ黒板に書く。(ここで、l_i,r_i は入力より与えられる非負整数である)
- 黒板に整数が 1 個以上書かれている間、高橋君を先手として交互に次の操作をする。
- 以下の 2 種類の操作のうちちょうど一方を選び、実行する。
- 黒板に書かれている偶数をすべて削除し、残った整数をそれぞれ 2 で割って小数点以下を切り捨てた値に書き換える。
- 黒板に書かれている奇数をすべて削除し、残った整数をそれぞれ 2 で割った値に書き換える。
- 以下の 2 種類の操作のうちちょうど一方を選び、実行する。
- 黒板に整数が 1 個も書かれていない状態になった場合、最後に操作をした人を勝者としてゲームを終了する。
高橋君と青木君が最適な行動を取った場合、ゲームは有限回の操作で終了することが示せます。この時の勝者を求めてください。
T ケースについて上記問題を解いてください。
制約
- 1 \leq T \leq 10^4
- 1 \leq N \leq 10^4
- 0 \leq l_i \leq r_i \leq 10^{18}
- r_i \lt l_{i+1}
- 1 つの入力に含まれるテストケースについて、N の総和は 10^4 以下
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ここで、\mathrm{test}_i は i 番目のテストケースを表す。
T
\mathrm{test}_1
\vdots
\mathrm{test}_T
各テストケースは以下の形式で与えられる。
N l_1 r_1 \vdots l_N r_N
出力
T 行出力せよ。i 行目には、i 番目のテストケースにおいて勝者が高橋君ならば Takahashi と、青木君ならば Aoki と出力せよ。
入力例 1
3 2 1 2 5 7 1 0 100 10 1312150450968413 28316250877914571 74859962623690078 84324828731963974 148049062628894320 252509054433933439 269587449430302150 335408917861648766 349993004923078531 354979173822804781 522842184971407769 578223540024979436 585335723211047194 615812229161735895 645762258982631926 760713016476190622 779547116602436424 819875141880895723 822981260158260519 919845426262703496
出力例 1
Aoki Aoki Takahashi
1 番目のテストケースに対するゲームの流れの例を以下に示します。
- 黒板に 1,2,5,6,7 が 1 個ずつ書かれる。
- 高橋君が奇数を削除する方の操作をする。黒板から 1,5,7 が削除され、残った整数 2,6 がそれぞれ 2 で割った値の 1,3 に書き換えられる。
- 青木君が奇数を削除する方の操作をする。黒板から 1,3 が削除され、黒板に整数が 1 個も書かれていない状態になったため最後に操作をした青木君を勝者としてゲームが終了する。
Score : 900 points
Problem Statement
Takahashi and Aoki will play the following game.
- For each i=1,2,\ldots,N in this order, do the following.
- Write each integer from l_i through r_i once on the blackboard. (Here, l_i and r_i are non-negative integers from the input.)
- While one or more integers are written on the blackboard, the players take turns doing the following, with Takahashi going first.
- Choose and perform exactly one of the following two operations.
- Delete all even numbers written on the blackboard, and replace each remaining integer with half its value rounded down to an integer.
- Delete all odd numbers written on the blackboard, and replace each remaining integer with half its value.
- Choose and perform exactly one of the following two operations.
- When no integer is written on the blackboard, the game ends and the last player to perform an operation wins.
It can be proved that the game ends in a finite number of operations if Takahashi and Aoki act optimally. Find the winner in this case.
Solve the above problem for T cases.
Constraints
- 1 \leq T \leq 10^4
- 1 \leq N \leq 10^4
- 0 \leq l_i \leq r_i \leq 10^{18}
- r_i \lt l_{i+1}
- The sum of N over the test cases in a single input is at most 10^4.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{test}_i represents the i-th test case:
T
\mathrm{test}_1
\vdots
\mathrm{test}_T
Each test case is given in the following format:
N l_1 r_1 \vdots l_N r_N
Output
Print T lines. The i-th line should contain Takahashi if Takahashi wins in the i-th test case, and Aoki if Aoki wins.
Sample Input 1
3 2 1 2 5 7 1 0 100 10 1312150450968413 28316250877914571 74859962623690078 84324828731963974 148049062628894320 252509054433933439 269587449430302150 335408917861648766 349993004923078531 354979173822804781 522842184971407769 578223540024979436 585335723211047194 615812229161735895 645762258982631926 760713016476190622 779547116602436424 819875141880895723 822981260158260519 919845426262703496
Sample Output 1
Aoki Aoki Takahashi
Here is an example of how the game goes for the first test case.
- Each of 1,2,5,6,7 is written once on the blackboard.
- Takahashi chooses to delete the odd numbers. 1,5,7 are deleted from the blackboard, and the remaining integers 2,6 are replaced by half their values, that is, 1,3, respectively.
- Aoki chooses to delete the odd numbers. 1,3 are deleted from the blackboard, and no more integer is written on the blackboard, so the game ends and Aoki, who performed the last operation, wins.