/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君と青木君が、いくつかの石からなる N 個の山を用いて石とりゲームで対戦します。
はじめ、i = 1, 2, \ldots, N について、i 番目の山は A_i 個の石からなります。 高橋君からはじめ、2 人は交互に次の行動をくりかえします。
石が 1 個以上残っている山を 1 つ選び、その山から 1 個以上の石を取り除く。
ただし、このゲームには M 種類の禁じ手があり、禁じ手に該当する行動を行うことはできません。
i = 1, 2, \ldots, M について、i 種類目の禁じ手は「ちょうど X_i 個の石からなる山からちょうど Y_i 個の石を取り除くこと」です。
先に行動を行うことができなくなった方のプレイヤーの負けとなり、負けなかった方のプレイヤーの勝ちとなります。 両者が自身が勝つために最適な戦略をとるとき、どちらのプレイヤーが勝つかを答えてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i \leq 10^{18}
- 1 \leq Y_i \leq X_i \leq 10^{18}
- i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N X_1 Y_1 X_2 Y_2 \vdots X_M Y_M
出力
両者が自身が勝つために最適な戦略をとるとき、高橋君が勝つならば Takahashi と、青木君が勝つならば Aoki と出力せよ。
入力例 1
3 4 1 2 4 2 1 3 3 3 1 1 1
出力例 1
Takahashi
i = 1, 2, 3 について、i 番目の山にある石の個数を A'_i とし、 それぞれの山にある石の個数を数列 A' = (A'_1, A'_2, A'_3) を用いて表すことにします。
ゲームが始まる前の時点では、A' = (1, 2, 4) です。ゲームの進行の一例として次のものがあります。
- まず、高橋君が 3 番目の山から石を 1 個取り除く。その結果、A' = (1, 2, 3) となる。
- 次に、青木君が 2 番目の山から石を 2 個取り除く。その結果、A' = (1, 0, 3) となる。
- さらに、高橋君が 3 番目の山から石を 2 個取り除く。その結果、A' = (1, 0, 1) となる。
その後の時点で、1 番目と 3 番目の山にはまだ石が 1 個ずつ残っていますが、ちょうど 1 個の石からなる山からちょうど 1 個の石を取り除くことは 4 種類目の禁じ手に該当するため、青木君は行動を行うことができません。したがって、高橋君の勝ちとなります。
入力例 2
1 5 5 5 1 5 2 5 3 5 4 5 5
出力例 2
Aoki
Score : 600 points
Problem Statement
Takahashi and Aoki will play a game against each other using N piles of stones.
Initially, for each i = 1, 2, \ldots, N, the i-th pile is composed of A_i stones. The players alternately perform the following action, with Takahashi going first.
- Choose a pile with at least one stone remaining, and remove one or more stones.
However, there are M forbidden moves.
For each i = 1, 2, \ldots, 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?
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i \leq 10^{18}
- 1 \leq Y_i \leq X_i \leq 10^{18}
- i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N X_1 Y_1 X_2 Y_2 \vdots 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.
Sample Input 1
3 4 1 2 4 2 1 3 3 3 1 1 1
Sample Output 1
Takahashi
For each i = 1, 2, 3, let A'_i be the number of stones remaining in the i-th pile. Now, we use the sequence A' = (A'_1, A'_2, A'_3) to represent the numbers of stones remaining in the piles.
Before the start of the game, we have A' = (1, 2, 4). One possible progression of the game is as follows.
- First, Takahashi removes 1 stone from the 3-rd pile. Now, A' = (1, 2, 3).
- Next, Aoki removes 2 stones from the 2-nd pile. Now, A' = (1, 0, 3).
- Then, Takahashi removes 2 stones from the 3-rd pile. Now, A' = (1, 0, 1).
At this point, the 1-st and 3-rd piles still have 1 stone each, but it is forbidden ー as the fourth forbidden move ー to remove exactly 1 stone from a pile composed of exactly 1 stone, so Aoki cannot play. Thus, Takahashi wins.
Sample Input 2
1 5 5 5 1 5 2 5 3 5 4 5 5
Sample Output 2
Aoki