E - カード取りゲーム 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君と青木君がカード取りゲームで対戦します。

テーブルの上には N 個のカードの束があり、i 番目の束には A_i 枚のカードが含まれています。また、1 回の手番で取り除けるカードの最大枚数 K が決められています。高橋君が先手です。

ゲームは以下のルールで進行します：

  • 先手と後手が交互に手番を行います。
  • 自分の手番では、カードが 1 枚以上残っている束を 1 つ選び、その束から 1 枚以上 K 枚以下のカードを取り除きます。ここで、各カードに区別はなく、束のカード枚数を選んだ枚数だけ減らす操作を行います。
  • 自分の手番のとき、すべての束のカードが 0 枚であり、カードを取り除くことができないプレイヤーの負けです。

両者が最適に行動したとき、勝者は高橋君と青木君のどちらでしょうか？

制約

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N K
A_1 A_2 \ldots A_N
  • 1 行目には、カードの束の数を表す整数 N と、1 回の手番で取り除けるカードの最大枚数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各束のカードの枚数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

両者が最適に行動したとき、高橋君が勝つ場合は Takahashi を、青木君が勝つ場合は Aoki を出力せよ。

入力例 1

2 3
4 5

出力例 1

Takahashi

入力例 2

3 2
3 6 9

出力例 2

Aoki

入力例 3

5 1000000000
1 2 3 4 5

出力例 3

Takahashi

Score : 433 pts

Problem Statement

Takahashi and Aoki are playing a card taking game against each other.

There are N piles of cards on the table, and the i-th pile contains A_i cards. A maximum number of cards K that can be removed in a single turn is also specified. Takahashi goes first.

The game proceeds according to the following rules:

  • The first player and the second player take turns alternately.
  • On your turn, choose one pile that has at least 1 card remaining, and remove between 1 and K cards (inclusive) from that pile. Here, individual cards are indistinguishable, and the operation simply reduces the number of cards in the chosen pile by the chosen amount.
  • The player who, on their turn, finds all piles with 0 cards and is unable to remove any cards, loses.

When both players play optimally, who wins — Takahashi or Aoki?

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All input values are integers

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of piles of cards, and an integer K representing the maximum number of cards that can be removed in a single turn, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the number of cards in each pile, separated by spaces.

Output

If Takahashi wins when both players play optimally, print Takahashi. If Aoki wins, print Aoki.

Sample Input 1

2 3
4 5

Sample Output 1

Takahashi

Sample Input 2

3 2
3 6 9

Sample Output 2

Aoki

Sample Input 3

5 1000000000
1 2 3 4 5

Sample Output 3

Takahashi