题目描述

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$ 人が最適に行動する時、どちらが勝つか判定してください。

输入格式

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

$N$ $S$ $X$

输出格式

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

题目大意

给定长度为 $N$（$1 \le N \le 2 \times 10^5$）的字符串 $S$（由数字 $0 \sim 9$ 组成），现在 Takahashi 要和 Aoki 进行 $N$ 轮游戏，第 $i$ 轮游戏可以让数字 $T$（初始时 $T=0$）变成 $10T$ 或 $10T+S_i$。

若游戏结束时 $T$ 是 $7$ 的倍数，则 Takahashi 获胜，否则 Aoki 获胜。

现在给了你字符串 $X$，在第 $i$ 轮时若 $X_i$ 为 $A$ 则由 Aoki 行动,为 $T$ 则由 Takahashi 行动，两人都会按照最优策略行动，问最后谁会获胜。

2
35
AT

Takahashi

5
12345
AAAAT

Aoki

5
67890
TTTTA

Takahashi

5
12345
ATATA

Aoki

提示

制約

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

Sample Explanation 1

$1$ 回目のラウンドでは青木君が 3 か 0 を $T$ の末尾に加え、$2$ 回目のラウンドでは高橋君が 5 か 0 を $T$ の末尾に加えます。 青木君が 3 を加えた場合、高橋君が 5 を追加すると $T$ は 35 となり、これは $7$ の倍数です。 青木君が 0 を加えた場合、高橋君が 0 を追加すると $T$ は 00 となり、これは $7$ の倍数です。 したがって、かならず高橋君が勝ちます。