7994: ABC255 —— G - Constrained Nim
[Creator : ]
Description
Takahashi and Aoki will play a game against each other using N piles of stones.
Initially, for each i=1,2,…,N, the i-th pile is composed of $A_i$ stones. The players alternately perform the following action, with Takahashi going first.
For each i=1,2,…,M, it is not allowed to remove exactly $Y_i$ stones from a pile composed of exactly $X_i$ stones.
The first player to become unable to perform the action loses, resulting in the other player's victory. Which player will win when both players employ the optimal strategy for the victory?
Initially, for each i=1,2,…,N, the i-th pile is composed of $A_i$ stones. The pla
- Choose a pile with at least one stone remaining, and remove one or more stones.
For each i=1,2,…,M, it is not allowed to remove exactly $Y_i$ stones from a pile composed of exactly $X_i$ stones.
The first pla
Input
Input is given from Standard Input in the following format:
$N\ M$
$A_1\ A_2\ …\ A_N$
$X_1\ Y_1$
$X_2\ Y_2$
$⋮$
$X_M\ Y_M$
$N\ M$
$A_1\ A_2\ …\ A_N$
$X_1\ Y_1$
$X_2\ Y_2$
$⋮$
$X_M\ Y_M$
Output
If Takahashi will win when both players employ the optimal strategy for the victory, print Takahashi; if Aoki will win, print Aoki.
Constraints
$1≤N≤2×10^5$
$1≤M≤2×10^5$
$1≤A_i≤10^{18}$
$1≤Y_i≤X_i≤10^{18}$
$i \neq j⇒(X_i,Y_i)\neq (X_j,Y_j)$
All values in input are integers.
$1≤M≤2×10^5$
$1≤A_i≤10^{18}$
$1≤Y_i≤X_i≤10^{18}$
$i \neq j⇒(X_i,Y_i)\neq (X_j,Y_j)$
All values in input are integers.
Sample 1 Input
3 4
1 2 4
2 1
3 3
3 1
1 1
Sample 1 Output
Takahashi
For each i=1,2,3, let $A_i^\prime$ be the number of stones remaining in the i-th pile. Now, we use the sequence $A^\prime=(A_1^\prime,A_2^\prime,A_3^\prime)$ to represent the numbers of stones remaining in the piles.
Before the start of the game, we have $A^\prime$=(1,2,4). One possible progression of the game is as follows.
Before the start of the game, we have $A^\prime$=(1,2,4). One possible progression of the game is as follows.
- First, Takahashi removes 1 stone from the 3-rd pile. Now, $A^\prime$=(1,2,3).
- Next, Aoki removes 2 stones from the 2-nd pile. Now, $A^\prime$=(1,0,3).
- Then, Takahashi removes 2 stones from the 3-rd pile. Now, $A^\prime$=(1,0,1).
Sample 2 Input
1 5
5
5 1
5 2
5 3
5 4
5 5
Sample 2 Output
Aoki