7 的倍数游戏

题目描述

给定由 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$ 后)解释为十进制表示的数时,如果它是 $7$ 的倍数则高桥君获胜,否则青木君获胜。

当两人都采取最优行动时,请判断谁会获胜。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$
$X$

输出格式

两人都采取最优行动时,如果高桥君获胜则输出 Takahashi,青木君获胜则输出 Aoki。

样例

2
35
AT

Takahashi

在第 $1$ 个回合中青木君在 $T$ 的末尾加入 3 或 0,在第 $2$ 个回合中高桥君在 $T$ 的末尾加入 5 或 0。

青木君加入 3 时,高桥君加入 5,则 $T$ 为 35,它是 $7$ 的倍数。

青木君加入 0 时,高桥君加入 0,则 $T$ 为 00,它是 $7$ 的倍数。

因此,一定是高桥君获胜。

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 组成