Problem Statement

There is a grid with H rows and W columns.

The square at the i-th row and j-th column contains a string S_{i,j} of length 5.

The rows are labeled with the numbers from 1 through H, and the columns are labeled with the uppercase English letters from A through the W-th letter of the alphabet.

Exactly one of the squares in the grid contains the string snuke. Find this square and report its location.

For example, the square at the 6-th row and 8-th column should be reported as H6.

Constraints

• 1≦H, W≦26
• The length of S_{i,j} is 5.
• S_{i,j} consists of lowercase English letters (a-z).
• Exactly one of the given strings is equal to snuke.

Sample Input 1

15 10
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snuke snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake

Sample Output 1

H6

Sample Input 2

1 1
snuke

Sample Output 2

A1

Problem Statement

The problem set at CODE FESTIVAL 20XX Finals consists of N problems.

The score allocated to the i-th (1≦i≦N) problem is i points.

Takahashi, a contestant, is trying to score exactly N points. For that, he is deciding which problems to solve.

As problems with higher scores are harder, he wants to minimize the highest score of a problem among the ones solved by him.

Determine the set of problems that should be solved.

Constraints

• 1≦N≦10^7

Partial Score

• 200 points will be awarded for passing the test set satisfying 1≦N≦1000.
• Additional 100 points will be awarded for passing the test set without additional constraints.

Sample Input 1

4

Sample Output 1

1
3

Solving only the 4-th problem will also result in the total score of 4 points, but solving the 1-st and 3-rd problems will lower the highest score of a solved problem.

Sample Input 2

7

Sample Output 2

1
2
4

The set \{3,4\} will also be accepted.

Sample Input 3

1

Sample Output 3

1

Problem Statement

On a planet far, far away, M languages are spoken. They are conveniently numbered 1 through M.

For CODE FESTIVAL 20XX held on this planet, N participants gathered from all over the planet.

The i-th (1≦i≦N) participant can speak K_i languages numbered L_{i,1}, L_{i,2}, ..., L_{i,{}K_i}.

Two participants A and B can communicate with each other if and only if one of the following conditions is satisfied:

• There exists a language that both A and B can speak.
• There exists a participant X that both A and B can communicate with.

Determine whether all N participants can communicate with all other participants.

Constraints

• 2≦N≦10^5
• 1≦M≦10^5
• 1≦K_i≦M
• (The sum of all K_i)≦10^5
• 1≦L_{i,j}≦M
• L_{i,1}, L_{i,2}, ..., L_{i,{}K_i} are pairwise distinct.

Partial Score

• 200 points will be awarded for passing the test set satisfying the following: N≦1000, M≦1000 and (The sum of all K_i)≦1000.
• Additional 200 points will be awarded for passing the test set without additional constraints.

Sample Input 1

4 6
3 1 2 3
2 4 2
2 4 6
1 6

Sample Output 1

YES

Any two participants can communicate with each other, as follows:

• Participants 1 and 2: both can speak language 2.
• Participants 2 and 3: both can speak language 4.
• Participants 1 and 3: both can communicate with participant 2.
• Participants 3 and 4: both can speak language 6.
• Participants 2 and 4: both can communicate with participant 3.
• Participants 1 and 4: both can communicate with participant 2.

Note that there can be languages spoken by no participant.

Sample Input 2

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

Sample Output 2

NO

For example, participants 1 and 3 cannot communicate with each other.

Problem Statement

Takahashi is playing with N cards.

The i-th card has an integer X_i on it.

Takahashi is trying to create as many pairs of cards as possible satisfying one of the following conditions:

• The integers on the two cards are the same.
• The sum of the integers on the two cards is a multiple of M.

Find the maximum number of pairs that can be created.

Note that a card cannot be used in more than one pair.

Constraints

• 2≦N≦10^5
• 1≦M≦10^5
• 1≦X_i≦10^5

Sample Input 1

7 5
3 1 4 1 5 9 2

Sample Output 1

3

Three pairs (3,2), (1,4) and (1,9) can be created.

It is possible to create pairs (3,2) and (1,1), but the number of pairs is not maximized with this.

Sample Input 2

15 10
1 5 6 10 11 11 11 20 21 25 25 26 99 99 99

Sample Output 2

6

Problem Statement

Rng is baking cookies.

Initially, he can bake one cookie per second.

He can also eat the cookies baked by himself. When there are x cookies not yet eaten, he can choose to eat all those cookies. After he finishes eating those cookies, the number of cookies he can bake per second becomes x. Note that a cookie always needs to be baked for 1 second, that is, he cannot bake a cookie in 1/x seconds when x > 1. When he choose to eat the cookies, he must eat all of them; he cannot choose to eat only part of them. It takes him A seconds to eat the cookies regardless of how many, during which no cookies can be baked.

He wants to give N cookies to Grandma. Find the shortest time needed to produce at least N cookies not yet eaten.

Constraints

• 1≦N≦10^{12}
• 0≦A≦10^{12}
• A is an integer.

Partial Score

• 500 points will be awarded for passing the test set satisfying N≦10^6 and A≦10^6.
• Additional 500 points will be awarded for passing the test set without additional constraints.

Sample Input 1

8 1

Sample Output 1

7

It is possible to produce 8 cookies in 7 seconds, as follows:

• After 1 second: 1 cookie is done.
• After 2 seconds: 1 more cookie is done, totaling 2. Now, Rng starts eating those 2 cookies.
• After 3 seconds: He finishes eating the cookies, and he can now bake 2 cookies per second.
• After 4 seconds: 2 cookies are done.
• After 5 seconds: 2 more cookies are done, totaling 4.
• After 6 seconds: 2 more cookies are done, totaling 6.
• After 7 seconds: 2 more cookies are done, totaling 8.

Sample Input 2

1000000000000 1000000000000

Sample Output 2

1000000000000

Problem Statement

There are N towns in Takahashi Kingdom. They are conveniently numbered 1 through N.

Takahashi the king is planning to go on a tour of inspection for M days. He will determine a sequence of towns c, and visit town c_i on the i-th day. That is, on the i-th day, he will travel from his current location to town c_i. If he is already at town c_i, he will stay at that town. His location just before the beginning of the tour is town 1, the capital. The tour ends at town c_M, without getting back to the capital.

The problem is that there is no paved road in this kingdom. He decided to resolve this issue by paving the road himself while traveling. When he travels from town a to town b, there will be a newly paved one-way road from town a to town b.

Since he cares for his people, he wants the following condition to be satisfied after his tour is over: "it is possible to travel from any town to any other town by traversing roads paved by him". How many sequences of towns c satisfy this condition?

Constraints

• 2≦N≦300
• 1≦M≦300

Sample Input 1

3 3

Sample Output 1

2

As shown below, the condition is satisfied only when c = (2,3,1) or c = (3,2,1). Sequences such as c = (2,3,2), c = (2,1,3), c = (1,2,2) do not satisfy the condition.

Sample Input 2

150 300

Sample Output 2

734286322

Sample Input 3

300 150

Sample Output 3

0

Problem Statement

We have a graph with N vertices, numbered 0 through N-1. Edges are yet to be added.

We will process Q queries to add edges. In the i-th (1≦i≦Q) query, three integers A_i, B_i and C_i will be given, and we will add infinitely many edges to the graph as follows:

• The two vertices numbered A_i and B_i will be connected by an edge with a weight of C_i.
• The two vertices numbered B_i and A_i+1 will be connected by an edge with a weight of C_i+1.
• The two vertices numbered A_i+1 and B_i+1 will be connected by an edge with a weight of C_i+2.
• The two vertices numbered B_i+1 and A_i+2 will be connected by an edge with a weight of C_i+3.
• The two vertices numbered A_i+2 and B_i+2 will be connected by an edge with a weight of C_i+4.
• The two vertices numbered B_i+2 and A_i+3 will be connected by an edge with a weight of C_i+5.
• The two vertices numbered A_i+3 and B_i+3 will be connected by an edge with a weight of C_i+6.
• ...

Here, consider the indices of the vertices modulo N. For example, the vertice numbered N is the one numbered 0, and the vertice numbered 2N-1 is the one numbered N-1.

The figure below shows the first seven edges added when N=16, A_i=7, B_i=14, C_i=1:

After processing all the queries, find the total weight of the edges contained in a minimum spanning tree of the graph.

Constraints

• 2≦N≦200,000
• 1≦Q≦200,000
• 0≦A_i,B_i≦N-1
• 1≦C_i≦10^9

Sample Input 1

7 1
5 2 1

Sample Output 1

21

The figure below shows the minimum spanning tree of the graph:

Note that there can be multiple edges connecting the same pair of vertices.

Sample Input 2

2 1
0 0 1000000000

Sample Output 2

1000000001

Also note that there can be self-loops.

Sample Input 3

5 3
0 1 10
0 2 10
0 4 10

Sample Output 3

42

Problem Statement

There are N squares in a row, numbered 1 through N from left to right. Snuke and Rng are playing a board game using these squares, described below:

1. First, Snuke writes an integer into each square.
2. Each of the two players possesses one piece. Snuke places his piece onto square 1, and Rng places his onto square 2.
3. The player whose piece is to the left of the opponent's, moves his piece. The destination must be a square to the right of the square where the piece is currently placed, and must not be a square where the opponent's piece is placed.
4. Repeat step 3. When the pieces cannot be moved any more, the game ends.
5. The score of each player is calculated as the sum of the integers written in the squares where the player has placed his piece before the end of the game.

Snuke has already written an integer A_i into square i (1≦i≦N-1), but not into square N yet. He has decided to calculate for each of M integers X_1,X_2,...,X_M, if he writes it into square N and the game is played, what the value "(Snuke's score) - (Rng's score)" will be. Here, it is assumed that each player moves his piece to maximize the value "(the player's score) - (the opponent's score)".

Constraints

• 3≦N≦200,000
• 0≦A_i≦10^6
• The sum of all A_i is at most 10^6.
• 1≦M≦200,000
• 0≦X_i≦10^9

Partial Scores

• 700 points will be awarded for passing the test set satisfying M=1.
• Additional 900 points will be awarded for passing the test set without additional constraints.

Sample Input 1

5
2 7 1 8
1
2

Sample Output 1

0

The game proceeds as follows, where S represents Snuke's piece, and R represents Rng's.

Both player scores 10, thus "(Snuke's score) - (Rng's score)" is 0.

Sample Input 2

9
2 0 1 6 1 1 2 6
5
2016
1
1
2
6

Sample Output 2

2001
6
6
7
7

Problem Statement

Snuke has a grid with H rows and W columns. The square at the i-th row and j-th column contains a character S_{i,j}.

He can perform the following two kinds of operation on the grid:

• Row-reverse: Reverse the order of the squares in a selected row.
• Column-reverse: Reverse the order of the squares in a selected column.

For example, reversing the 2-nd row followed by reversing the 4-th column will result as follows:

By performing these operations any number of times in any order, how many placements of characters on the grid can be obtained?

Constraints

• 1≦H,W≦200
• S_{i,j} is a lowercase English letter (a-z).

Sample Input 1

2 2
cf
cf

Sample Output 1

6

The following 6 placements of characters can be obtained:

Sample Input 2

1 12
codefestival

Sample Output 2

2

Problem Statement

Snuke has a board with an N \times N grid, and N \times N tiles.

Each side of a square that is part of the perimeter of the grid is attached with a socket. That is, each side of the grid is attached with N sockets, for the total of 4 \times N sockets. These sockets are labeled as follows:

• The sockets on the top side of the grid: U1, U2, ..., UN from left to right
• The sockets on the bottom side of the grid: D1, D2, ..., DN from left to right
• The sockets on the left side of the grid: L1, L2, ..., LN from top to bottom
• The sockets on the right side of the grid: R1, R2, ..., RN from top to bottom

Snuke can insert a tile from each socket into the square on which the socket is attached. When the square is already occupied by a tile, the occupying tile will be pushed into the next square, and when the next square is also occupied by another tile, that another occupying tile will be pushed as well, and so forth. Snuke cannot insert a tile if it would result in a tile pushed out of the grid. The behavior of tiles when a tile is inserted is demonstrated in detail at Sample Input/Output 1.

Snuke is trying to insert the N \times N tiles one by one from the sockets, to reach the state where every square contains a tile. Here, he must insert exactly U_i tiles from socket Ui, D_i tiles from socket Di, L_i tiles from socket Li and R_i tiles from socket Ri. Determine whether it is possible to insert the tiles under the restriction. If it is possible, in what order the tiles should be inserted from the sockets?

Constraints

• 1≦N≦300
• U_i,D_i,L_i and R_i are non-negative integers.
• The sum of all values U_i,D_i,L_i and R_i is equal to N \times N.

Partial Scores

• 2000 points will be awarded for passing the test set satisfying N≦40.
• Additional 100 points will be awarded for passing the test set without additional constraints.

Sample Input 1

3
0 0 1
1 1 0
3 0 1
0 1 1

Sample Output 1

L1
L1
L1
L3
D1
R2
U3
R3
D2

Snuke can insert the tiles as shown in the figure below. An arrow indicates where a tile is inserted from, a circle represents a tile, and a number written in a circle indicates how many tiles are inserted before and including the tile.

Sample Input 2

2
2 0
2 0
0 0
0 0

Sample Output 2

NO