Problem Statement

Takahashi will have N penalty kicks in a soccer match.

For the i-th penalty kick, he will fail if i is a multiple of 3, and succeed otherwise.

Print the results of his penalty kicks.

Constraints

• 1 \leq N \leq 100
• All inputs are integers.

Sample Input 1

7

Sample Output 1

ooxooxo

Takahashi fails the third and sixth penalty kicks, so the third and sixth characters will be x.

Sample Input 2

9

Sample Output 2

ooxooxoox

Problem Statement

You are given a positive integer N.

Output N, N-1, \dots, 1 in this order, separated by commas ,.

Constraints

• 1 \leq N \leq 9
• N is an integer.

Sample Input 1

9

Sample Output 1

9,8,7,6,5,4,3,2,1

Sample Input 2

5

Sample Output 2

5,4,3,2,1

Sample Input 3

1

Sample Output 3

1

Problem Statement

Takahashi is at the origin on a two-dimensional coordinate plane.

The cost for him to move from point (a, b) to point (c, d) is \sqrt{(a - c)^2 + (b - d)^2}.

Find the total cost when he starts at the origin, visits N points (X_1, Y_1), \ldots, (X_N, Y_N) in this order, and then returns to the origin.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i, Y_i \leq 10^9
• All input values are integers.

Sample Input 1

2
1 2
-1 0

Sample Output 1

6.06449510224597979401

The journey consists of the following three steps:

• Move from (0, 0) to (1, 2). The cost is \sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977....
• Move from (1, 2) to (-1, 0). The cost is \sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124....
• Move from (-1, 0) to (0, 0). The cost is \sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1.

The total cost is 6.064495102....

Sample Input 2

7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

Sample Output 2

384694.57587932075868509383

Sample Input 3

5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

Sample Output 3

1414213.56237309504880168872

Problem Statement

Locate a piece on a chessboard.

We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.

• The first character of the name of a square in the 1-st column from the left is a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left is b, c, d, e, f, g, h, respectively.
• The second character of the name of a square in the 1-st row from the bottom is 1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is 2, 3, 4, 5, 6, 7, 8, respectively.

For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.

You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise. The character * occurs exactly once among S_1,\ldots,S_8. Find the name of the square that has a piece on it.

Constraints

• S_i is a string of length 8 consisting of . and*.
• The character * occurs exactly once among S_1,\ldots,S_8.

Sample Input 1

........
........
........
........
........
........
........
*.......

Sample Output 1

a1

As explained in the problem statement, the bottom-left square is named a1.

Sample Input 2

........
........
........
........
........
.*......
........
........

Sample Output 2

b3

Problem Statement

There is a slot machine with N reels.
The placement of symbols on the i-th reel is represented by a string S_i of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can press one of the buttons of his choice (or do nothing) t seconds after the reels start spinning.
If the button for the i-th reel is pressed t seconds after the start of the spin, the i-th reel will stop to display the ((t\bmod{10})+1)-th character of S_i.
Here, t\bmod{10} denotes the remainder when t is divided by 10.

Takahashi wants to stop all reels to make them display the same character.
Find the minimum number of seconds needed to achieve his objective after the start of the spin.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Sample Input 1

3
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can make all reels display 8 in 6 seconds after the start of the spin by stopping them as follows.

• 0 seconds after the start of the spin, press the button for the 2-nd reel, making it stop to display the ((0\bmod{10})+1=1)-st character of S_2, 8.
• 2 seconds after the start of the spin, press the button for the 3-rd reel, making it stop to display the ((2\bmod{10})+1=3)-rd character of S_3, 8.
• 6 seconds after the start of the spin, press the button for the 1-st reel, making it stop to display the ((6\bmod{10})+1=7)-th character of S_1, 8.

There is no way to make all reels display the same character in five seconds or less, so the answer is 6.

Sample Input 2

5
0123456789
0123456789
0123456789
0123456789
0123456789

Sample Output 2

40

Note that he must stop all reels to make them display the same character.

Problem Statement

Ringo-san is trying to paint a horse with stripes to make it a zebra.

There are N squares numbered 1 to N arranged in a line.
Initially, all squares are white, and the cost of painting square i black is C_i.

Consider performing the following procedure once to paint some squares black:

• Choose a positive integer x freely.
• Paint square i black for all integers i satisfying 1 \leq i \leq N such that the remainder when (i+x) is divided by 2W is less than W.

Find the minimum total cost to perform this procedure.

You are given T test cases; solve each of them.

Constraints

• 1\leq T \leq 2\times 10^5
• 1\leq N \leq 2\times 10^5
• 1\leq W \leq 2\times 10^5
• 1\leq C_i \leq 10^9
• The sum of N over the T test cases is at most 2\times 10^5.
• The sum of W over the T test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

4
8 2
1 10 10 1 1 10 10 1
8 3
1 10 10 1 1 10 10 1
8 4
1 10 10 1 1 10 10 1
4 100
100000 100000 100000 100000

Sample Output 1

4
12
22
0

In the first test case, if the procedure is executed with x=4, squares 1,4,5,8 are painted black, and the total cost is 4. The total cost cannot be less than 4, so this is the minimum.

Problem Statement

Takahashi is about to go buy eel at a fish shop.

The town where he lives is divided into a grid of H rows and W columns. Each cell is either a road or a wall.
Let us denote the cell at the i-th row from the top (1\leq i \leq H) and the j-th column from the left (1\leq j \leq W) as cell (i,j).
Information about each cell is given by H strings S_1,S_2,\ldots,S_H, each of length W. Specifically, if the j-th character of S_i (1\leq i \leq H,1\leq j\leq W) is ., cell (i,j) is a road; if it is #, cell (i,j) is a wall.

He can repeatedly perform the following two types of actions in any order:

• Move to an adjacent cell (up, down, left, or right) that is within the town and is a road.
• Choose one of the four directions (up, down, left, or right) and perform a front kick in that direction.
  When he performs a front kick, for each of the cells at most 2 steps away in that direction from the cell he is currently in, if that cell is a wall, it becomes a road.
  If some of the cells at most 2 steps away are outside the town, a front kick can still be performed, but anything outside the town does not change.

He starts in cell (A,B), and he wants to move to the fish shop in cell (C,D).
It is guaranteed that both the cell where he starts and the cell with the fish shop are roads.
Find the minimum number of front kicks he needs in order to reach the fish shop.

Constraints

• 1\leq H\leq 1000
• 1\leq W\leq 1000
• Each S_i is a string of length W consisting of . and #.
• 1\leq A,C\leq H
• 1\leq B,D\leq W
• (A,B)\neq (C,D)
• H, W, A, B, C, and D are integers.
• The cell where Takahashi starts and the cell with the fish shop are roads.

Sample Input 1

10 10
..........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
.##.#.#.#.
###.#.#.#.
###.#.#.#.
#.....#...
1 1 7 1

Sample Output 1

1

Takahashi starts in cell (1,1).
By repeatedly moving to adjacent road cells, he can reach cell (7,4).
If he performs a front kick to the left from cell (7,4), cells (7,3) and (7,2) turn from walls to roads.
Then, by continuing to move through road cells (including those that have become roads), he can reach the fish shop in cell (7,1).

In this case, the number of front kicks performed is 1, and it is impossible to reach the fish shop without performing any front kicks, so print 1.

Sample Input 2

2 2
.#
#.
1 1 2 2

Sample Output 2

1

Takahashi starts in cell (1,1).
When he performs a front kick to the right, cell (1,2) turns from a wall to a road.
The cell two steps to the right of (1,1) is outside the town, so it does not change.
Then, he can move to cell (1,2) and then to the fish shop in cell (2,2).

In this case, the number of front kicks performed is 1, and it is impossible to reach the fish shop without performing any front kicks, so print 1.

Sample Input 3

1 3
.#.
1 1 1 3

Sample Output 3

1

When performing a front kick, it is fine if the fish shop’s cell is within the cells that could be turned into a road. Specifically, the fish shop’s cell is a road from the beginning, so it remains unchanged; particularly, the shop is not destroyed by the front kick.

Sample Input 4

20 20
####################
##...##....###...###
#.....#.....#.....##
#..#..#..#..#..#..##
#..#..#....##..#####
#.....#.....#..#####
#.....#..#..#..#..##
#..#..#.....#.....##
#..#..#....###...###
####################
####################
##..#..##...###...##
##..#..#.....#.....#
##..#..#..#..#..#..#
##..#..#..#..#..#..#
##.....#..#..#..#..#
###....#..#..#..#..#
#####..#.....#.....#
#####..##...###...##
####################
3 3 18 18

Sample Output 4

3

Problem Statement

There are N servers numbered from 1 to N and M cables numbered from 1 to M.
Cable i connects servers A_i and B_i bidirectionally.

By performing the following operation some number of times (possibly zero), make all servers connected via cables.

• Operation: Choose one cable and reconnect one of its ends to a different server.

Find the minimum number of operations required and output an operation sequence achieving this minimum.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i, B_i \leq N
• All input values are integers.

Sample Input 1

4 5
1 1
1 2
2 1
3 4
4 4

Sample Output 1

1
1 1 3

By reconnecting the end of cable 1 that is connected to server 1 to server 3, the servers can be connected via cables.

Operations such as reconnecting the end of cable 5 that is connected to server 4 to server 1, or reconnecting the end of cable 2 that is connected to server 2 to server 3, will also result in all servers being connected and are considered correct.

Sample Input 2

4 3
3 4
4 1
1 2

Sample Output 2

0

No operation may be necessary.

Sample Input 3

5 4
3 3
3 3
3 3
3 3

Sample Output 3

4
1 3 5
2 3 4
3 3 2
4 3 1

Problem Statement

You are given an integer array A=(a_1,a_2,\ldots,a_N).
You may perform the following operation any number of times (possibly zero).

• Choose a nonempty contiguous subarray of A, and delete it from the array.

For each x=1,2,\ldots,M, solve the following problem:

• Find the minimum possible number of operations to make the sum of elements of A equal x. If it is impossible to make the sum of elements of A equal x, print -1 instead.

Note that the sum of elements of an empty array is 0.

Constraints

• 1 \leq N,M \leq 3000
• 1 \leq a_i \leq 3000
• All values in the input are integers.

Sample Input 1

4 5
1 2 3 4

Sample Output 1

1
2
1
1
1

The followings are examples of minimum number of operations that achieve the goal.

• For x=1, delete a_2,a_3,a_4, and the sum of elements of A becomes x.
• For x=2, delete a_3,a_4, then delete a_1, and the sum of elements of A becomes x.
• For x=3, delete a_3,a_4, and the sum of elements of A becomes x.
• For x=4, delete a_1,a_2,a_3, and the sum of elements of A becomes x.
• For x=5, delete a_2,a_3, and the sum of elements of A becomes x.

Sample Input 2

1 5
3

Sample Output 2

-1
-1
0
-1
-1

Sample Input 3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

Sample Output 3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1