Loading [MathJax]/jax/output/HTML-CSS/jax.js

Home


Contest: Task: Related: TaskD TaskF

Score : 500 points

Problem Statement

We have a string S of length N consisting of 0, , 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 (1iN), the following happens:

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

After N operations, T will be a string of length N consisting of 0, , 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

  • 1N2×105
  • S and X have a length of N each.
  • S consists of 0, , 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
'],['\\(','\\)']], processEscapes: true, skipTags: ['prepp'], processClass: "mathjax", ignoreClass: "no-mathjax" } });