Problem Statement

AtCoder Grand Contest (AGC), a regularly held contest with a world authority, has been held 54 times.

Just like the 230-th ABC ― the one you are in now ― is called ABC230, the N-th AGC is initially named with a zero-padded 3-digit number N. (The 1-st AGC is AGC001, the 2-nd AGC is AGC002, ...)

However, the latest 54-th AGC is called AGC055, where the number is one greater than 54. Because AGC042 is canceled and missing due to the social situation, the 42-th and subsequent contests are assigned numbers that are one greater than the numbers of contests held. (See also the explanations at Sample Inputs and Outputs.)

Here is the problem: given an integer N, print the name of the N-th AGC in the format AGCXXX, where XXX is the zero-padded 3-digit number.

Constraints

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

Sample Input 1

42

Sample Output 1

AGC043

As explained in Problem Statement, the 42-th and subsequent AGCs are assigned numbers that are one greater than the numbers of contests.
Thus, the 42-th AGC is named AGC043.

Sample Input 2

19

Sample Output 2

AGC019

The 41-th and preceding AGCs are assigned numbers that are equal to the numbers of contests.
Thus, the answer is AGC019.

Sample Input 3

1

Sample Output 3

AGC001

As mentioned in Problem Statement, the 1-st AGC is named AGC001.
Be sure to pad the number with zeros into a 3-digit number.

Sample Input 4

50

Sample Output 4

AGC051

Problem Statement

The ASCII values of the lowercase English letters a, b, \ldots, z are 97,98,\ldots,122 in this order.

Given an integer N between 97 and 122, print the letter whose ASCII value is N.

Constraints

• N is an integer between 97 and 122 (inclusive).

Sample Input 1

97

Sample Output 1

a

97 is the ASCII value of a.

Sample Input 2

122

Sample Output 2

z

Problem Statement

You are trying to implement collision detection in a 3D game.

In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)

Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.

Constraints

• 0 \leq a < d \leq 1000
• 0 \leq b < e \leq 1000
• 0 \leq c < f \leq 1000
• 0 \leq g < j \leq 1000
• 0 \leq h < k \leq 1000
• 0 \leq i < l \leq 1000
• All input values are integers.

Sample Input 1

0 0 0 4 5 6
2 3 4 5 6 7

Sample Output 1

Yes

The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.

Sample Input 2

0 0 0 2 2 2
0 0 2 2 2 4

Sample Output 2

No

The two cuboids touch at a face, where the volume of the intersection is 0.

Sample Input 3

0 0 0 1000 1000 1000
10 10 10 100 100 100

Sample Output 3

Yes

Problem Statement

Takahashi ate N plates of sushi at a sushi restaurant. The color of the i-th plate is represented by a string C_i.

The price of a sushi corresponds to the color of the plate. For each i=1,\ldots,M, the sushi on a plate whose color is represented by a string D_i is worth P_i yen a plate (yen is the currency of Japan). If the color does not coincide with any of D_1,\ldots, and D_M, it is worth P_0 yen a plate.

Find the total amount of the prices of sushi that Takahashi ate.

Constraints

• 1\leq N,M\leq 100
• C_i and D_i are strings of length between 1 and 20, inclusive, consisting of lowercase English letters.
• D_1,\ldots, and D_M are distinct.
• 1\leq P_i\leq 10000
• N, M, and P_i are integers.

Sample Input 1

3 2
red green blue
blue red
800 1600 2800

Sample Output 1

5200

A blue plate, red plate, and green plate are worth P_1 = 1600, P_2 = 2800, and P_0 = 800 yen, respectively.

The total amount of the prices of the sushi that he ate is 2800+800+1600=5200 yen.

Sample Input 2

3 2
code queen atcoder
king queen
10 1 1

Sample Output 2

21

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3
3 5 2
26

Sample Output 1

8

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

23

Problem Statement

There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.

Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.

Here, achieving Bingo means satisfying at least one of the following conditions:

• There exists a row in which all N cells are marked.
• There exists a column in which all N cells are marked.
• There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.

Constraints

• 2 \leq N \leq 2 \times 10^3
• 1 \leq T \leq \min(N^2, 2 \times 10^5)
• 1 \leq A_i \leq N^2
• A_i \neq A_j if i \neq j.
• All input values are integers.

Sample Input 1

3 5
5 1 8 9 7

Sample Output 1

4

The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.

Sample Input 2

3 5
4 2 9 7 5

Sample Output 2

-1

Bingo is not achieved within five turns, so print -1.

Sample Input 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

Sample Output 3

9

Problem Statement

There are N trampolines on a two-dimensional planar town where Takahashi lives. The i-th trampoline is located at the point (x_i, y_i) and has a power of P_i. Takahashi's jumping ability is denoted by S. Initially, S=0. Every time Takahashi trains, S increases by 1.

Takahashi can jump from the i-th to the j-th trampoline if and only if:

• P_iS\geq |x_i - x_j| +|y_i - y_j|.

Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.

At least how many times does he need to train to achieve his objective?

Constraints

• 2 \leq N \leq 200
• -10^9 \leq x_i,y_i \leq 10^9
• 1 \leq P_i \leq 10^9
• (x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
• All values in input are integers.

Sample Input 1

4
-10 0 1
0 0 5
10 0 1
11 0 1

Sample Output 1

2

If he trains twice, S=2, in which case he can reach any trampoline from the 2-nd one.

For example, he can reach the 4-th trampoline as follows.

• Jump from the 2-nd to the 3-rd trampoline. (Since P_2 S = 10 and |x_2-x_3| + |y_2-y_3| = 10, it holds that P_2 S \geq |x_2-x_3| + |y_2-y_3|.)

• Jump from the 3-rd to the 4-th trampoline. (Since P_3 S = 2 and |x_3-x_4| + |y_3-y_4| = 1, it holds that P_3 S \geq |x_3-x_4| + |y_3-y_4|.)

Sample Input 2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

Sample Output 2

18

Problem Statement

There is an island of size H \times W, surrounded by the sea.
The island is divided into H rows and W columns of 1 \times 1 sections, and the elevation of the section at the i-th row from the top and the j-th column from the left (relative to the current sea level) is A_{i,j}.

Starting from now, the sea level rises by 1 each year.
Here, a section that is vertically or horizontally adjacent to the sea or a section sunk into the sea and has an elevation not greater than the sea level will sink into the sea.
Here, when a section newly sinks into the sea, any vertically or horizontally adjacent section with an elevation not greater than the sea level will also sink into the sea simultaneously, and this process repeats for the newly sunk sections.

For each i=1,2,\ldots, Y, find the area of the island that remains above sea level i years from now.

Constraints

• 1 \leq H, W \leq 1000
• 1 \leq Y \leq 10^5
• 1 \leq A_{i,j} \leq 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

9
7
6
5
4

Let (i,j) denote the section at the i-th row from the top and the j-th column from the left. Then, the following happens:

• After 1 year, the sea level is higher than now by 1, but there are no sections with an elevation of 1 that are adjacent to the sea, so no sections sink. Thus, the first line should contain 9.
• After 2 years, the sea level is higher than now by 2, and (1,2) sinks into the sea. This makes (2,2) adjacent to a sunken section, and its elevation is not greater than 2, so it also sinks. No other sections sink at this point. Thus, two sections sink, and the second line should contain 9-2=7.
• After 3 years, the sea level is higher than now by 3, and (2,1) sinks into the sea. No other sections sink. Thus, the third line should contain 6.
• After 4 years, the sea level is higher than now by 4, and (2,3) sinks into the sea. No other sections sink. Thus, the fourth line should contain 5.
• After 5 years, the sea level is higher than now by 5, and (3,2) sinks into the sea. No other sections sink. Thus, the fifth line should contain 4.

Therefore, print 9, 7, 6, 5, 4 in this order, each on a new line.

Sample Input 2

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

Sample Output 2

15
7
0

Problem Statement

This is an interactive problem (where your program and the judge program interact through Standard Input and Output).

There is a simple connected undirected graph with N vertices and M edges. The vertices are numbered with integers from 1 to N.

Initially, you are at vertex 1. Repeat moving to an adjacent vertex at most 2N times to reach vertex N.

Here, you do not initially know all edges of the graph, but you will be informed of the vertices adjacent to the vertex you are at.

Constraints

• 2\leq N\leq100
• N-1\leq M\leq\dfrac{N(N-1)}2
• The graph is simple and connected.
• All input values are integers.

Input and Output

First, receive the number of vertices N and the number of edges M in the graph from Standard Input:

N M

Next, you get to repeat the operation described in the problem statement at most 2N times against the judge.

At the beginning of each operation, the vertices adjacent to the vertex you are currently at are given from Standard Input in the following format:

k v _ 1 v _ 2 \ldots v _ k

Here, v _ i\ (1\leq i\leq k) are integers between 1 and N such that v _ 1\lt v _ 2\lt\cdots\lt v _ k.

Choose one of v _ i\ (1\leq i\leq k) and print it to Standard Output in the following format:

v _ i

After this operation, you will be at vertex v _ i.

If you perform more than 2N operations or print invalid output, the judge will send -1 to Standard Input.

If the destination of a move is vertex N, the judge will send OK to Standard Input and terminate.

When receiving -1 or OK, immediately terminate the program.

Notes

• In each output, insert a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
• The verdict will be indeterminate if the program prints invalid output or quits prematurely in the middle of the interaction.
• Terminate the program immediately after reaching vertex N. Otherwise, the verdict will be indeterminate.
• The judge for this problem is adaptive. This means that the graph may change without contradicting the constraints or previous outputs.

Sample Interaction

In the following sample interaction, we have N=4, M=5, and the graph in the figure below.

You will be judged as correct if you immediately terminate the program after receiving OK.