#abc349e. E - Weighted Tic-Tac-Toe

E - Weighted Tic-Tac-Toe

Score: 450450 points

问题陈述

有一个 3×33 \times 3 的网格。用 (i,j)(i, j) 表示从顶部数第 ii 行,从左边数第 jj 列的单元格 (1i,j3)(1 \leq i, j \leq 3)。单元格 (i,j)(i, j) 包含一个整数 Ai,jA_{i,j}。保证 i=13j=13Ai,j\sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} 是奇数。此外,所有单元格最初都涂成白色。

高桥和青木将使用这个网格进行游戏。高桥先手,他们轮流执行以下操作:

  • 选择一个仍然涂成白色的单元格 (i,j)(i, j) (1i,j3)(1\leq i, j \leq 3)(可以证明在操作时总是存在这样的单元格)。执行操作的玩家得分 Ai,jA_{i,j} 分。然后,如果玩家是高桥,他将单元格 (i,j)(i, j) 涂成红色;如果玩家是青木,他将其涂成蓝色。

每次操作后,会进行以下检查:

  • 检查是否有三个连续的单元格涂成相同的颜色(红色或蓝色)在任何行、列或对角线上。如果存在这样的序列,游戏立即结束,形成序列颜色的玩家获胜。
  • 检查是否还有白色单元格。如果没有白色单元格剩余,游戏结束,总分高的玩家获胜。

可以证明,游戏总是在有限的回合后结束,高桥或青木中的一个将获胜。如果两个玩家都为了胜利而最优地玩,确定哪个玩家会赢。

以上为大语言模型 kimi 翻译,仅供参考。

Problem Statement

There is a 3×33 \times 3 grid. Let (i,j)(i, j) denote the cell at the ii-th row from the top and jj-th column from the left (1i,j3)(1 \leq i, j \leq 3). Cell (i,j)(i, j) contains an integer Ai,jA_{i,j}. It is guaranteed that i=13j=13Ai,j\sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd. Additionally, all cells are initially painted white.

Takahashi and Aoki will play a game using this grid. Takahashi goes first, and they take turns performing the following operation:

  • Choose a cell (i,j)(i, j) (1i,j3)(1\leq i, j \leq 3) that is still painted white (it can be shown that such a cell always exists at the time of the operation). The player performing the operation scores Ai,jA_{i,j} points. Then, if the player is Takahashi, he paints the cell (i,j)(i, j) red; if the player is Aoki, he paints it blue.

After each operation, the following checks are made:

  • Check if there are three consecutive cells painted the same color (red or blue) in any row, column, or diagonal. If such a sequence exists, the game ends immediately, and the player whose color forms the sequence wins.
  • Check if there are white cells left. If no white cells remain, the game ends, and the player with the higher total score wins.

It can be shown that the game will always end after a finite number of moves, and either Takahashi or Aoki will win. Determine which player wins if both play optimally for victory.

Constraints

  • Ai,j109|A_{i,j}| \leq 10^9
  • i=13j=13Ai,j\sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

A1,1A_{1,1} A1,2A_{1,2} A1,3A_{1,3}

A2,1A_{2,1} A2,2A_{2,2} A2,3A_{2,3}

A3,1A_{3,1} A3,2A_{3,2} A3,3A_{3,3}

Output

If Takahashi wins, print Takahashi; if Aoki wins, print Aoki.

Sample Input 1

0 0 0
0 1 0
0 0 0

Sample Output 1

Takahashi

If Takahashi chooses cell (2,2)(2,2) in his first move, no matter how Aoki plays afterward, Takahashi can always act to prevent three consecutive blue cells. If three consecutive red cells are formed, Takahashi wins. If the game ends without three consecutive red cells, at that point, Takahashi has scored 11 point and Aoki 00 points, so Takahashi wins either way.

Sample Input 2

-1 1 0
-4 -2 -5
-4 -1 -5

Sample Output 2

Aoki