Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given are distinct integers A, B, and C. Which of them is the second greatest? Answer with A, B, or C.

Constraints

• 1 \le A, B, C \le 100
• A, B, and C are distinct integers.

Sample Input 1

15 49 7

Sample Output 1

A

The second greatest is A = 15.

Sample Input 2

53 2 1

Sample Output 2

B

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have a calculator. When you enter non-negative integers X and Y, it shows the value \frac{X}{Y} without leading zeros after rounding down (towards negative infinity) to two decimal places. For example, if X=4,Y=2, the calculator shows 2.00; if X=2,Y=3, it shows 0.66. If Y=0, it shows ERROR.

Write a program to find what the calculator shows when X and Y are entered.

Constraints

• All values in input are integers.
• 0 \leq X, Y \leq 100

Sample Input 1

100 3

Sample Output 1

33.33

• We have \frac{X}{Y}= 33.33333 \cdots. The calculator rounds it down to two decimal places and shows 33.33.

Sample Input 2

42 0

Sample Output 2

ERROR

• Print ERROR if Y=0.

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a grid with N rows and M columns. Each square has # or . written on it. More specifically, the square at the i-th row from the top and j-th column from the left has s_{i,j} written on it. For each square T, count the number of squares with # among the following squares (at most nine in total): T itself, and the squares that are horizontally, vertically, or diagonally adjacent to T.

Constraints

• 1 \leq N,M \leq 30
• The length of s_i (1 \leq i \leq N) is M.
• s_{i,j} is # or ..

Sample Input 1

3 4
#.##
..#.
#...

Sample Output 1

1333
2433
1211

• For example, consider the square at the 1-st row from the top and 3-rd column from the left. Among that square and the ones that are horizontally, vertically, or diagonally adjacent to that square, there are 3 squares with #.
• Thus, the 3-rd character from the beginning in the 1-st line should be 3.

Sample Input 2

10 12
#.##..#...##
#..#..##...#
##.#....##.#
.#..###...#.
#..#..#...##
###...#..###
.###.#######
.#..#....###
.#.##..####.
.###....#..#

Sample Output 2

233322331133
455432343354
444344443343
444344332454
454335431465
466434554686
466434445796
346554457885
346542135664
235431134432

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N squares arranged in a row from left to right. Let Square i be the i-th square from the left. There are ninjas in some squares. The positions of the ninjas are given as a string S. If the i-th character of S is #, there is a ninja in Square i; if that character is ., there is no ninja in Square i. We can now do two types of operations, A and B, any number of times, possibly zero, in any order.

• Type A: Every ninja who is not in Square 1 creates his clone in the square to the immediate left of him. The clone will be treated as a real ninja from then on.
• Type B: Every ninja who is not in Square N creates his clone in the square to the immediate right of him. The clone will be treated as a real ninja from then on.

Let x and y be the numbers of times the operations of Type A and B are performed, respectively. Consider the sequences of operations after which there is at least one ninja in every square. Find x and y in one of those sequences of operations that minimizes x + y.

Constraints

• 1 \le N \le 50
• N is an integer.
• S consists of . and #.
• S contains at least one #.

Sample Input 1

5
.#..#

Sample Output 1

1 1

For example, if we first do Type A and then Type B, whether each square contains a ninja changes as follows: .#..# -> ##.## -> #####, and every square contains ninja eventually. It is impossible to achieve this objective with less than two operations in total, so this is a valid answer. There are also other valid answers; one of them is 2 0.

Sample Input 2

6
..#...

Sample Output 2

2 3

This is the only valid answer.

Sample Input 3

3
###

Sample Output 3

0 0

It is possible that no cloning is needed.

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string S. Determine whether there is a string T that satisfies all of the following conditions, and find one such string if it exists.

• T is a permutation of characters of S.
• T is different from S.
• The reversal of T is different from S.

Constraints

• 1 \le N \le 5
• N is an integer.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3
cba

Sample Output 1

acb

acb is a permutation of cba, and both itself and its reversal differ from cba, so it satisfies the conditions. Other strings such as bac also satisfy the conditions, but strings such as xyz, cba, and abc do not.

Sample Input 2

2
aa

Sample Output 2

None

No string satisfies the conditions.

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a sequence S of N words that form a certain sentence. The same word may appear multiple times in this sequence. Consider sorting the words that appear at least once in S in descending order of frequency, and print the word that comes in K-th. However, if the K-th frequent word varies depending on the order of words with the same frequency, print AMBIGUOUS instead.

Constraints

• 1 \le N \le 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters. (1 \le i \le N)
• 1 \le K \le ( the number of different words contained in S)
• N and K are integers.

Sample Input 1

6 2
abcde
caac
abcde
caac
abc
caac

Sample Output 1

abcde

caac appears three times, abcde appears twice, and abc appears once. The second most frequent word is abcde.

Sample Input 2

9 3
a
a
bb
bb
a
ccc
bb
ccc
dddd

Sample Output 2

ccc

a and bb appear three times each, c appears twice, and dddd appears once. Regardless of the order of a and bb, that have the same frequency, these two come first and second, and ccc comes third, so we should print ccc.

Sample Input 3

7 2
caac
abcde
caac
abc
abcde
caac
abc

Sample Output 3

AMBIGUOUS

caac appears three times, and abcde and abc appear twice each. The second frequent word is not uniquely determined - it can be abcde or abc, so we should print AMBIGUOUS.

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

AtCoder Village is divided into a rectangular grid with N rows going east-west and M columns going north-south, for a total of N \times M squares. Some of the squares are "wall squares". If S_{i, j} is #, the square at the i-th row and j-th column is a wall square; if S_{i, j} is ., that square is not a wall square. You will change exactly one of the wall squares to a non-wall square. Find the number of wall squares that you can choose to change if the following condition must be satisfied after the change:

• For every pair of two non-wall squares, it is possible to travel between those squares by repeatedly moving one square up, down, left, or right, only passing through non-wall squares in the village.

Constraints

• 1 \le N \le 10
• 1 \le M \le 10
• N and M are integers.
• S_i is a string of length M consisting of # and .. (1 \le i \le N)
• There is at least one wall square and at least one non-wall square.

Sample Input 1

3 3
..#
#..
.##

Sample Output 1

2

For example, if you change the square at the 2-nd row from the north and 1-st column from the west to a non-wall square, it will be possible to travel between every pair of non-wall squares. You can also choose the square at the 3-rd row from the north and 2-nd column from the west to satisfy the condition. There is no other such wall square, so the answer is 2.

Sample Input 2

3 3
##.
##.
...

Sample Output 2

3

Every wall square except the one at the north-west corner can be chosen to satisfy the condition. Note that it must be possible to travel between every pair of two non-wall squares, including the new non-wall square you make.

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a grid of squares with N rows and M columns. Each square has a digit written on it; the digit written on the square at the i-th row from the top and j-th column from the left is s_{i,j}. Your work is to choose an integer n and cut out a square-shaped grid of squares with n rows and n columns where all squares have the same digit written on them.

What is the maximum possible value of n when you can choose at most K squares and change the digits written on those squares?

Constraints

• 1 \leq N,M \leq 30
• 0 \leq K \leq NM
• The length of s_i (1 \leq i \leq N) is M.
• s_{i,j} is one of the digits 0123456789.

Sample Input 1

3 4 3
1123
1214
1810

Sample Output 1

3

• Let (i,j) denotes the square at the i-th row from the top and j-th column from the left.
• If you change the digits written on (1,3), (2,2), and (3,2), there will be a subgrid with 3 rows and 3 columns where all squares have 1 written on them.

Sample Input 2

8 6 40
846444
790187
264253
967004
578258
204367
681998
034243

Sample Output 2

6

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Your dinner today is a pizza. There are N pieces of the pizza, numbered 1 through N, arranged clockwise in this order. Note that Piece N and Piece 1 are adjacent to each other.

The deliciousness of Piece i is a_i.

You will choose some consecutive pieces and eat them. For example, if the pizza has 10 pieces, you can choose the pieces 8,9,10,1,2 and eat them, but cannot choose 1,3,5.

Find the minimum possible value of |X-Y| where X and Y are the sum of the deliciousness of the pieces you eat and that of the remaining pieces, respectively.

Constraints

• All values in input are integers.
• 2 \leq N \leq 2 \times 10^5
• 1 \leq a_i \leq 10^9

Sample Input 1

4
10 20 40 30

Sample Output 1

20

• One optimal choice is to choose to eat the pieces 4,1,2.
• Here, the sum of the deliciousness of the pieces you eat, X, is 30+10+20=60, and that of the remaining pieces, Y, is 40, resulting in |X-Y|=20.
• Note that neither choosing the pieces 1,3 nor choosing 2,4 is allowed since those sets of pieces are not consecutive.

Sample Input 2

20
13 76 46 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9

Sample Output 2

1

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N towns numbered 1 through N, and M roads. The i-th road connects Town A_i and Town B_i bidirectionally, and you get C_i points of fatigue when you pass through that road. For every pair of towns, there is at most one road that directly connects those towns, and it is possible to travel between those towns by traversing some roads. Additionally, each town has a teleporter of type A, type B, or type C. The placement of teleporters is given to you by a string S; the teleporter in Town i is of type S_i. There may be some types of teleporters that do not exist in any towns. You can teleport between two towns with different types of teleporters. When you do so, you get the following points of fatigue:

• X_{\mathrm{AB}} points when teleporting between towns with teleporters of type A and type B;
• X_{\mathrm{AC}} points when teleporting between towns with teleporters of type A and type C;
• X_{\mathrm{BC}} points when teleporting between towns with teleporters of type B and type C.

You cannot teleport between towns with the same type of teleporter. Find the minimum possible total points of fatigue you get when going from Town 1 to Town N only using roads and teleporters.

Constraints

• 2 \le N \le 10^5
• 1 \le M \le 10^5
• 1 \le X_{\mathrm{AB}}, X_{\mathrm{AC}}, X_{\mathrm{BC}} \le 10^9
• S is a string of length N consisting of A, B, and C.
• 1 \le A_i \le N
• 1 \le B_i \le N
• A_i \neq B_i
• 1 \le C_i \le 10^9
• For every pair of towns, there is at most one road that directly connects those towns.
• For every pair of towns, it is possible to travel between those towns by traversing some roads.
• All values in input, except S, are integers.

Sample Input 1

3 2
10 10 10
ABA
1 2 15
2 3 5

Sample Output 1

15

If you first teleport from Town 1 (type A) to Town 2 (type B) and then use the 2-nd road to go from Town 2 to Town 3, you get 10 + 5 = 15 points of fatigue, which is optimal. Note that both Town 1 and Town 3 have a teleporter of type A, so you cannot directly teleport between them.

Sample Input 2

3 2
10 1000000000 10
ABC
1 2 1000000000
2 3 1000000000

Sample Output 2

20

If you first teleport from Town 1 (type A) to Town 2 (type B) and from Town 2 (type B) to Town C (type C), you will get 10 + 10 = 20 points of fatigue, which is optimal. Note that you can teleport from Town 1 to Town 3 directly this time, but it is not optimal since teleporting from a teleporter of type A to that of type C costs X_{\mathrm{AC}} = 1000000000 points of fatigue.

Sample Input 3

5 6
5 10 15
ABCBC
5 4 4
3 5 2
1 3 7
3 4 1
4 2 1
2 3 3

Sample Output 3

8

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have K number sequences called a_1 through a_K. The length of the sequence a_i is n_i, and its j-th element is a_{i,j}.

Using those sequences, you have decided to make a new sequence x. Initially, the length of x is 0.

You will do Q operations. In the i-th of them, you will replace x with the result of concatenating the sequence a_{b_i} to the end of x.

Let |x| denotes the length of x. Find the number of pairs of integers (i,j) such that 1 \leq i < j \leq |x| and x_i > x_j after all the operations. Since it can be enormous, print it modulo 10^9.

Constraints

• All values in input are integers.
• 1 \leq K,Q \leq 10^5
• 1 \leq n_i \leq 10^5
• 1 \leq a_{i,j} \leq 20
• 1 \leq b_i \leq K
• \sum_{i=1}^{K} n_i \leq 3 \times 10^5

Sample Input 1

2
3
1 3 2
2
5 4
2
1 2

Sample Output 1

2

• Initially, x is empty.
• In the 1-st operation, x is replaced with the concatenation of x and (1,3,2), that is, (1,3,2).
• In the 2-st operation, x is replaced with the concatenation of x and (5,4), that is, (1,3,2,5,4).
• Now, there are two pairs (i,j) such that 1 \leq i < j \leq |x| and x_i > x_j: (2,3) and (4,5).

Sample Input 2

10
8
16 6 15 10 18 13 17 11
13
4 10 6 4 14 17 13 9 3 9 4 8 14
11
11 17 12 3 13 8 10 11 18 2 19
10
18 11 16 19 4 17 7 3 5 8
3
3 10 9
13
8 17 20 8 20 1 5 17 4 16 18 20 4
15
11 2 1 16 8 17 4 7 3 6 4 13 16 16 16
2
12 12
8
7 14 7 5 8 17 19 4
15
3 6 1 16 11 5 3 15 9 15 12 15 5 19 7
20
4 3 7 6 1 8 2 3 9 8 6 3 10 9 7 7 3 2 2 10

Sample Output 2

12430

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N apartments numbered 1 through N, standing in a row in this order. Initially, the height of Apartment i is h_i.

Q operations will be done sequentially. The type of the i-th operation is represented by t_{i}, as follows:

• If t_i=1: Given an integer v_i, increase the height of every odd-numbered apartment (Apartment 1, 3, ...) by v_i.
• If t_i=2: Given an integer v_i, increase the height of every even-numbered apartment (Apartment 2, 4, ...) by v_i.
• If t_i=2: Given integers u_i and v_i, increase the height of Apartment u_i apartment by v_i.

For each operation, find the number of integers i satisfying 1 \leq i < N such that the heights of Apartment i and Apartment i+1 are equal at the end of the operation.

Constraints

• All values in input are integers.
• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq h_i, v_i \leq 10^9
• t_i is 1, 2, or 3.
• 1 \leq u_i \leq N

Sample Input 1

4 2
10 20 30 20
1 10
3 4 20

Sample Output 1

1
2

• Initially, the heights of the apartments 1,2,3,4 are 10,20,30,20, respectively.
• In the 1-st operation, the heights of the odd-numbered apartments change, resulting in the heights of the apartments being 20,20,40,20.
  • Now there is one integer i such that the heights of Apartment i and Apartment i+1 are equal: 1.
• In the 2-nd operation, the height of Apartment 4 changes, resulting in the heights of the apartments being 20,20,40,40.
  • Now there are two integers i such that the heights of Apartment i and Apartment i+1 are equal: 1,3.

Sample Input 2

10 20
108 112 112 110 110 109 108 110 111 112
3 4 2
1 1
3 9 1
3 4 2
2 1
1 1
3 7 2
2 1
3 8 2
1 1
2 1
1 1
3 10 2
3 6 1
2 1
3 7 1
1 1
2 1
3 3 2
3 3 2

Sample Output 2

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

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a tree with N vertices numbered 1 through N. The tree has N-1 edges numbered 1 through N-1, and Edge i connects Vertex a_i and b_i bidirectionally. Each edge can be painted in a color represented by an integer between 0 and 10^5 (inclusive). Initially, every edge is painted in Color 0.

Q operations will be done on this tree. In the i-th operation, the color of every edge on the shortest path from Vertex u_i to Vertex v_i becomes Color c_i.

Examine the color of the edges 1, 2, \ldots, N-1 after the Q operations.

Constraints

• All values in input are integers.
• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq a_i, b_i,u_i,v_i \leq N
• u_i \neq v_i
• 1 \leq c_i \leq 10^5
• The given graph is a tree.

Sample Input 1

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

Sample Output 1

5
10
0

• Initially, every edge is painted in Color 0.
• In the first operation, Edge 1 and Edge 2 are repainted in Color 10.
• In the second operation, Edge 1 is repainted in Color 5.
• In the end, the edges 1, 2, and 3 are painted in Color 5, 10, and 0, respectively.

Sample Input 2

10 10
7 2
5 8
8 6
8 3
8 9
9 1
4 8
4 10
8 7
7 5 12773
2 6 74733
1 6 64470
7 2 41311
1 9 39776
4 8 71709
9 1 23551
4 6 29181
3 7 23742
8 4 54686

Sample Output 2

41311
12773
29181
23742
64470
23551
54686
0
23742

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a grid with 18 rows and 6 columns. Each square has 0, 1, or ? written on it; written on the square at the i-th row from the top and j-th column from the left is s_{i,j}.

How many ways are there to replace each ? written on a square with 0 or 1 so that the grid will satisfy the following condition?

Condition: The number written on each square is equal to the median of the numbers written on the following five squares: the square itself and the squares horizontally or vertically adjacent to the square. (Assume that the area outside the grid is filled by squares with 0 written on them.)

Constraints

• s_{i,j} is 0, 1, or ?.

Sample Input 1

??0000
??0000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000

Sample Output 1

2

• The condition is satisfied only if we write 0 in every ? square or write 1 in every ? square.

Sample Input 2

???000
???000
???000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000

Sample Output 2

16

Sample Input 3

?01000
1101?1
100111
1?11??
???00?
00011?
1?1??1
000101
100?11
1010??
?101??
?1??10
????10
?1??0?
1?1???
110?1?
0000?0
001?10

Sample Output 3

0

• There is no way to write numbers that satisfies the condition.

Sample Input 4

??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????

Sample Output 4

243882696958399859

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have found N treasure chests numbered 1 through N. Initially, all the chests are locked and cannot be opened. If you manage to unlock Chest i, you get a_i yen (the currency of Japan).

Among your friends, there are M locksmiths, numbered 1 through M. If you ask Locksmith i to unlock chests by paying c_i yen, the locksmith will unlock all chests that are still locked among the chests l_i, l_i + 1, \ldots, r_i.

Your objective is to maximize Y-X, where X is the total amount of money you pay to locksmiths, and Y is the total amount of money you get from chests. Find the maximum possible value of Y-X.

Constraints

• All values in input are integers.
• 1 \leq N,M \leq 2 \times 10^5
• 1 \leq a_i,c_i \leq 10^9
• 1 \leq l_i \leq r_i \leq N

Sample Input 1

4 3
20 10 100 10
1 3 100
2 4 50
1 1 50

Sample Output 1

70

• It is optimal to pay 50 yen to Locksmith 2 and get 10+100+10=120 yen from unlocking the chests 2,3,4.
• Note that you do not have to unlock all the chests.

Sample Input 2

2 2
10 10
1 1 1000
1 2 100

Sample Output 2

0

• Note that the optimal strategy might be not asking any locksmiths to unlock chests.

Sample Input 3

20 10
40 28 12 29 34 89 37 64 48 53 81 95 46 42 77 76 49 59 14 15
2 11 221
14 20 14
2 11 126
1 8 273
5 11 94
2 8 48
12 15 83
2 7 13
5 16 269
3 12 115

Sample Output 3

760