Score : 900 points
Takahashi and Aoki are playing a stone-taking game. Initially, there are N piles of stones, and the i-th pile contains A_i stones and has an associated integer K_i.
Starting from Takahashi, Takahashi and Aoki take alternate turns to perform the following operation:
The player who first becomes unable to perform the operation loses the game. Assuming that both players play optimally, determine the winner of the game. Here, floor(x) represents the largest integer not greater than x.
Input is given from Standard Input in the following format:
N A_1 K_1 : A_N K_N
If Takahashi will win, print Takahashi
; if Aoki will win, print Aoki
.
2 5 2 3 3
Aoki
Initially, from the first pile at most floor(5/2)=2 stones can be removed at a time, and from the second pile at most floor(3/3)=1 stone can be removed at a time.
No more operation can be performed, thus Aoki wins. If Takahashi plays differently, Aoki can also win by play accordingly.
3 3 2 4 3 5 1
Takahashi
3 28 3 16 4 19 2
Aoki
4 3141 59 26535 897 93 23 8462 64
Takahashi