Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

• 1 \leq |S| \leq 5\times 10^5
• S consists of lowercase English letters.
• T is obtained by inserting a lowercase English letter into S.

Sample Input 1

atcoder
atcorder

Sample Output 1

5

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

5

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

3

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

You are given a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell is one of the following: a start cell, a goal cell, an empty cell, or an obstacle cell. This information is described by H strings S_1,S_2,\dots,S_H, each of length W. Specifically, the cell (i,j) is a start cell if the j-th character of S_i is S, a goal cell if it is G, an empty cell if it is ., and an obstacle cell if it is #. It is guaranteed that there is exactly one start cell and exactly one goal cell.

You are currently on the start cell. Your objective is to reach the goal cell by repeatedly moving to a cell adjacent by an edge to the one you are in. However, you cannot move onto an obstacle cell or move outside the grid, and you must alternate between moving vertically and moving horizontally each time. (The direction of the first move can be chosen arbitrarily.)

Determine if it is possible to reach the goal cell. If it is, find the minimum number of moves required.

More formally, check if there exists a sequence of cells (i_1,j_1),(i_2,j_2),\dots,(i_k,j_k) satisfying all of the following conditions. If such a sequence exists, find the minimum value of k-1.

• For every 1 \leq l \leq k, it holds that 1 \leq i_l \leq H and 1 \leq j_l \leq W, and (i_l,j_l) is not an obstacle cell.
• (i_1,j_1) is the start cell.
• (i_k,j_k) is the goal cell.
• For every 1 \leq l \leq k-1, |i_l - i_{l+1}| + |j_l - j_{l+1}| = 1.
• For every 1 \leq l \leq k-2, if i_l \neq i_{l+1}, then i_{l+1} = i_{l+2}.
• For every 1 \leq l \leq k-2, if j_l \neq j_{l+1}, then j_{l+1} = j_{l+2}.

Constraints

• 1 \leq H,W \leq 1000
• H and W are integers.
• Each S_i is a string of length W consisting of S, G, ., #.
• There is exactly one start cell and exactly one goal cell.

Sample Input 1

3 5
.S#.G
.....
.#...

Sample Output 1

7

As shown in the left figure, you can move as (1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(3,4)\rightarrow(2,4)\rightarrow(2,5)\rightarrow(1,5), reaching the goal cell in 7 moves. It is impossible in 6 moves or fewer, so the answer is 7.

Note that you cannot take a path that moves horizontally (or vertically) consecutively without alternating as shown in the right figure.

Sample Input 2

3 5
..#.G
.....
S#...

Sample Output 2

-1

It is not possible to reach the goal cell.

Sample Input 3

8 63
...............................................................
..S...#............................#####..#####..#####..####G..
..#...#................................#..#...#......#..#......
..#####..####...####..####..#..#...#####..#...#..#####..#####..
..#...#..#..#...#..#..#..#..#..#...#......#...#..#..........#..
..#...#..#####..####..####..####...#####..#####..#####..#####..
................#.....#........#...............................
................#.....#........#...............................

Sample Output 3

148

Problem Statement

There is a 3 \times 3 grid. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left (1 \leq i, j \leq 3). Cell (i, j) contains an integer A_{i,j}. It is guaranteed that \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) (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 A_{i,j} points. Then, if the player is Takahashi, he paints the cell (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

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

Sample Input 1

0 0 0
0 1 0
0 0 0

Sample Output 1

Takahashi

If Takahashi chooses cell (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 1 point and Aoki 0 points, so Takahashi wins either way.

Sample Input 2

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

Sample Output 2

Aoki

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N), where each element is at least 2. Anna and Bruno play a game using these integers. They take turns, with Anna going first, performing the following operation.

• Choose an integer i \ (1 \leq i \leq N) freely. Then, freely choose a positive divisor x of A_i that is not A_i itself, and replace A_i with x.

The player who cannot perform the operation loses, and the other player wins. Determine who wins assuming both players play optimally for victory.

Constraints

• 1 \leq N \leq 10^5
• 2 \leq A_i \leq 10^5
• All input values are integers.

Sample Input 1

3
2 3 4

Sample Output 1

Anna

For example, the game might proceed as follows. Note that this example may not necessarily represent optimal play by both players:

• Anna changes A_3 to 2.
• Bruno changes A_1 to 1.
• Anna changes A_2 to 1.
• Bruno changes A_3 to 1.
• Anna cannot operate on her turn, so Bruno wins.

Actually, for this sample, Anna always wins if she plays optimally.

Sample Input 2

4
2 3 4 6

Sample Output 2

Bruno