E - Lucky 7 Battle 解説 /

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

配点 : 500 点

問題文

0,\ldots,9 からなる長さ N の文字列 S と、A,T からなる長さ N の文字列 X が与えられます。また、空文字列で初期化された文字列 T があります。

高橋君と青木君がこれらを使ってゲームをします。ゲームは N ラウンドからなり、i 回目 (1\leq i \leq N) のラウンドでは次の操作が行われます。

  • X_i が A なら青木君が、T なら高橋君が以下の操作を行う
  • 操作：T の末尾に S_i か 0 のどちらか一方を加える

N 回の操作が終了したあと、T は 0,\ldots,9 からなる長さ N の文字列となります。 T を (先頭の余計な 0 を取り除いた上で) 10 進法で表された数と解釈したとき、7 の倍数であれば高橋君の勝ちであり、そうでなければ青木君の勝ちです。

2 人が最適に行動する時、どちらが勝つか判定してください。

制約

  • 1 \leq N \leq 2\times 10^5
  • S,X の長さは N
  • S は 0,\ldots,9 のみからなる
  • X は A,T のみからなる

入力

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

N
S
X

出力

2 人が最適に行動する時、高橋君が勝つなら Takahashi、 青木君が勝つなら Aoki と出力せよ。

入力例 1

2
35
AT

出力例 1

Takahashi

1 回目のラウンドでは青木君が 3 か 0 を T の末尾に加え、2 回目のラウンドでは高橋君が 5 か 0 を T の末尾に加えます。

青木君が 3 を加えた場合、高橋君が 5 を追加すると T は 35 となり、これは 7 の倍数です。

青木君が 0 を加えた場合、高橋君が 0 を追加すると T は 00 となり、これは 7 の倍数です。

したがって、かならず高橋君が勝ちます。

入力例 2

5
12345
AAAAT

出力例 2

Aoki

入力例 3

5
67890
TTTTA

出力例 3

Takahashi

入力例 4

5
12345
ATATA

出力例 4

Aoki

Score : 500 points

Problem Statement

We have a string S of length N consisting of 0, \ldots, 9, and a string X of length N consisting of A and T. Additionally, there is a string T, which is initialized to an empty string.

Takahashi and Aoki will play a game using these. The game consists of N rounds. In the i-th round (1\leq i \leq N), the following happens:

  • If X_i is A, Aoki does the operation below; if X_i is T, Takahashi does it.
  • Operation: append S_i or 0 at the end of T.

After N operations, T will be a string of length N consisting of 0, \ldots, 9. If T is a multiple of 7 as a base-ten number (after removing leading zeros), Takahashi wins; otherwise, Aoki wins.

Determine the winner of the game when the two players play optimally.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • S and X have a length of N each.
  • S consists of 0, \ldots, 9.
  • X consists of A and T.

Input

Input is given from Standard Input in the following format:

N
S
X

Output

If Takahashi wins when the two players play optimally, print Takahashi; if Aoki wins, print Aoki.

Sample Input 1

2
35
AT

Sample Output 1

Takahashi

In the 1-st round, Aoki appends 3 or 0 at the end of T. In the 2-nd round, Takahashi appends 5 or 0 at the end of T.

If Aoki appends 3, Takahashi can append 5 to make T 35, a multiple of 7.

If Aoki appends 0, Takahashi can append 0 to make T 00, a multiple of 7.

Thus, Takahashi can always win.

Sample Input 2

5
12345
AAAAT

Sample Output 2

Aoki

Sample Input 3

5
67890
TTTTA

Sample Output 3

Takahashi

Sample Input 4

5
12345
ATATA

Sample Output 4

Aoki