B - Bouzu Mekuri Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

N 枚のカードからなる山札があります。
それぞれのカードは、「良いカード」か「悪いカード」かのどちらかです。

高橋君と青木君は、この山札を使って対戦ゲームをします。
このゲームでは、2 人は交互に山札の一番上のカードを引いて、そのカードを食べます。
先に悪いカードを食べたプレイヤーの負けです。（ここで、山札には少なくとも 1 枚の悪いカードが含まれていることが保証されます。）

0 と 1 からなる文字列 S が与えられます。i = 1, 2, \ldots, N について、

  • S の i 文字目が 0 のとき、山札の上から i 番目のカードが良いカードであることを表します。
  • S の i 文字目が 1 のとき、山札の上から i 番目のカードが悪いカードであることを表します。

高橋君が先手でゲームを始めるとき、高橋君と青木君のどちらが負けるかを答えてください。

制約

  • 1 \leq N \leq 10^5
  • N は整数
  • S は 0 と 1 からなる長さ N の文字列
  • S は少なくとも 1 個の 1 を含む。

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

高橋君が先手でゲームを始めるとき、高橋君と青木君のどちらが負けるかを答えよ。
高橋君が負けるならば Takahashi 、青木君が負けるならば Aoki と出力せよ。

入力例 1

5
00101

出力例 1

Takahashi

まず、高橋君が良いカードを食べ、次に青木君が良いカードを食べ、その後に高橋君が悪いカードを食べます。
高橋君が先に悪いカードを食べるので高橋君が負けます。よって、Takahashi と出力します。

入力例 2

3
010

出力例 2

Aoki

Score : 200 points

Problem Statement

We have a deck of N cards.
Each of these cards is good or bad.

Using this deck, Takahashi and Aoki will play a game against each other.
In the game, the players alternately draw the topmost card and eat it.
The player who first gets to eat a bad card loses the game. (Here, it is guaranteed that the deck contains at least one bad card.)

You are given a string S consisting of 0 and 1. For each i = 1, 2, \ldots, N,

  • if the i-th character of S is 0, it means that the i-th card from the top of the deck is good;
  • if the i-th character of S is 1, it means that the i-th card from the top of the deck is bad.

Which player will lose when Takahashi goes first in the game?

Constraints

  • 1 \leq N \leq 10^5
  • N is an integer.
  • S is a string of length N consisting of 0 and 1.
  • S contains at least one occurrence of 1.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the name of the player who will lose when Takahashi goes first in the game: Takahashi or Aoki.

Sample Input 1

5
00101

Sample Output 1

Takahashi

First, Takahashi will eat a good card. Next, Aoki will eat a good card. Then, Takahashi will eat a bad card.
Thus, Takahashi will be the first to eat a bad card, so we should print Takahashi.

Sample Input 2

3
010

Sample Output 2

Aoki