E - 幸运7大战

分数：500分

问题描述

我们有一个长度为$N$的字符串$S$，由0，$\ldots$，9组成，还有一个长度为$N$的字符串$X$，由A和T组成。此外，有一个字符串$T$，其初始化为空字符串。

高桥和青木将使用这些进行一场游戏。游戏由$N$轮组成。在第$i$轮（$1\leq i \leq N$）中，发生以下情况：

• 如果$X_i$是A，则青木进行如下操作；如果$X_i$是T，则高桥进行如下操作。
• 操作：将$S_i$或0附加到$T$的末尾。

经过$N$次操作，$T$将成为长度为$N$的由0，$\ldots$，9组成的字符串。如果将$T$视为十进制数时是$7$的倍数（在去除前导零后），则高桥获胜，否则青木获胜。

确定当两位玩家采取最优策略时游戏的获胜者。

约束

• $1 \leq N \leq 2\times 10^5$
• $S$和$X$的长度均为$N$。
• $S$由0，$\ldots$，9组成。
• $X$由A和T组成。

输入

输入以以下格式从标准输入中给出：

$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