Problem Statement

You are given a string S of even length consisting of lowercase English letters. Let |S| be the length of S, and S_i be the i-th character of S.

Perform the following operation for each i = 1, 2, \ldots, \frac{|S|}{2} in this order, and print the final S.

• Swap S_{2i-1} and S_{2i}.

Constraints

• S is a string of even length consisting of lowercase English letters.
• The length of S is at most 100.

Sample Input 1

abcdef

Sample Output 1

badcfe

Initially, S = abcdef.
Performing the operation for i = 1 swaps S_1 and S_2, making S = bacdef.
Performing the operation for i = 2 swaps S_3 and S_4, making S = badcef.
Performing the operation for i = 3 swaps S_5 and S_6, making S = badcfe.
Thus, badcfe should be printed.

Sample Input 2

aaaa

Sample Output 2

aaaa

Sample Input 3

atcoderbeginnercontest

Sample Output 3

taocedbrgeniencrnoetts

Problem Statement

Given integers A and B, find A+B.
This is a N-choice problem; the i-th choice is C_i.
Print the index of the correct choice.

Constraints

• All values in the input are integers.
• 1 \le N \le 300
• 1 \le A,B \le 1000
• 1 \le C_i \le 2000
• C_i are pairwise distinct. In other words, no two choices have the same value.
• There is exactly one i such that A+B=C_i. In other words, there is always a unique correct choice.

Sample Input 1

3 125 175
200 300 400

Sample Output 1

2

We have 125+175 = 300.
The first, second, and third choices are 200, 300, and 400, respectively.
Thus, the 2-nd choice is correct, so 2 should be printed.

Sample Input 2

1 1 1
2

Sample Output 2

1

The problem may be a one-choice problem.

Sample Input 3

5 123 456
135 246 357 468 579

Sample Output 3

5

Problem Statement

We have a circular pizza.
Takahashi will cut this pizza using a sequence A of length N, according to the following procedure.

• First, make a cut from the center in the 12 o'clock direction.
• Next, do N operations. The i-th operation is as follows.
  • Rotate the pizza A_i degrees clockwise.
  • Then, make a cut from the center in the 12 o'clock direction.

For example, if A=(90,180,45,195), the procedure cuts the pizza as follows.

Find the center angle of the largest pizza after the procedure.

Constraints

• All values in input are integers.
• 1 \le N \le 359
• 1 \le A_i \le 359
• There will be no multiple cuts at the same position.

Sample Input 1

4
90 180 45 195

Sample Output 1

120

This input coincides with the example in the Problem Statement.
The center angle of the largest pizza is 120 degrees.

Sample Input 2

1
1

Sample Output 2

359

Sample Input 3

10
215 137 320 339 341 41 44 18 241 149

Sample Output 3

170

Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

• The string contains an uppercase English alphabet.
• The string contains a lowercase English alphabet.
• All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of uppercase and lowercase English alphabets.

Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.

Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.

Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

There is a grid with H rows and W columns.

Each cell of the grid is land or sea, which is represented by H strings S_1, S_2, \ldots, S_H of length W. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left, and (i, j) is land if the j-th character of S_i is ., and (i, j) is sea if the character is #.

The constraints guarantee that all cells on the perimeter of the grid (that is, the cells (i, j) that satisfy at least one of i = 1, i = H, j = 1, j = W) are sea.

Takahashi's spaceship has crash-landed on a cell in the grid. Afterward, he moved N times on the grid following the instructions represented by a string T of length N consisting of L, R, U, and D. For i = 1, 2, \ldots, N, the i-th character of T describes the i-th move as follows:

• L indicates a move of one cell to the left. That is, if he is at (i, j) before the move, he will be at (i, j-1) after the move.
• R indicates a move of one cell to the right. That is, if he is at (i, j) before the move, he will be at (i, j+1) after the move.
• U indicates a move of one cell up. That is, if he is at (i, j) before the move, he will be at (i-1, j) after the move.
• D indicates a move of one cell down. That is, if he is at (i, j) before the move, he will be at (i+1, j) after the move.

It is known that all cells along his path (including the cell where he crash-landed and the cell he is currently on) are not sea. Print the number of cells that could be his current position.

Constraints

• H, W, and N are integers.
• 3 \leq H, W \leq 500
• 1 \leq N \leq 500
• T is a string of length N consisting of L, R, U, and D.
• S_i is a string of length W consisting of . and #.
• There is at least one cell that could be Takahashi's current position.
• All cells on the perimeter of the grid are sea.

Sample Input 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

Sample Output 1

2

The following two cases are possible, so there are two cells that could be Takahashi's current position: (3, 4) and (4, 5).

• He crash-landed on cell (3, 5) and moved (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
• He crash-landed on cell (4, 6) and moved (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

Sample Input 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

Sample Output 2

6

Problem Statement

Takahashi has N cards in his hand. For i = 1, 2, \ldots, N, the i-th card has an non-negative integer A_i written on it.

First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).

• Let X be the integer written on the last card put on the table. If his hand contains cards with the integer X or the integer (X+1)\bmod M written on them, freely choose one of those cards and put it on the table. Here, (X+1)\bmod M denotes the remainder when (X+1) is divided by M.

Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 10^9
• 0 \leq A_i \lt M
• All values in the input are integers.

Sample Input 1

9 7
3 0 2 5 5 3 0 6 3

Sample Output 1

11

Assume that he first puts the fourth card (5 is written) on the table and then performs the following.

• Put the fifth card (5 is written) on the table.
• Put the eighth card (6 is written) on the table.
• Put the second card (0 is written) on the table.
• Put the seventh card (0 is written) on the table.

Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is 3 + 2 + 3 +3 = 11. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.

Sample Input 2

1 10
4

Sample Output 2

0

Sample Input 3

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

Sample Output 3

99

Problem Statement

You are given an undirected graph with N vertices and M edges. The vertices are numbered 1,2,\ldots,N, and the i‑th edge (1 \le i \le M) connects vertices u_i and v_i.

For each k = 1,2,\ldots,N, solve the following problem:

Consider the following operation.

• Choose one vertex, and delete that vertex together with all edges incident to it.

Determine whether one can repeat this operation to satisfy the following condition:

• The set of vertices reachable from vertex 1 by traversing edges consists exactly of the k vertices 1,2,\ldots,k.

If it is possible, find the minimum number of operations required to do so.

Constraints

• 1 \le N \le 2 \times 10^{5}
• 0 \le M \le 3 \times 10^{5}
• 1 \le u_i < v_i \le N\ (1 \le i \le M)
• (u_i,v_i) \ne (u_j,v_j)\ (1 \le i < j \le M)
• All input values are integers.

Sample Input 1

6 7
1 2
1 5
2 3
2 4
2 5
3 6
5 6

Sample Output 1

2
3
3
2
1
0

For example, for k = 2, deleting the three vertices 3, 4, 5 makes the set of vertices reachable from vertex 1 equal to the two vertices 1, 2. It is impossible with two or fewer deletions, so print 3 on the 2nd line.

For k = 6, deleting zero vertices makes the set of vertices reachable from vertex 1 equal to the six vertices 1,2,\ldots,6, so print 0 on the 6th line.

Sample Input 2

5 4
1 5
2 3
3 4
4 5

Sample Output 2

1
-1
-1
-1
0

Sample Input 3

2 0

Sample Output 3

0
-1

There may be no edges.

Sample Input 4

11 25
6 9
5 9
2 3
1 9
10 11
4 5
9 10
8 9
7 8
3 5
1 7
6 10
4 7
7 9
1 10
4 11
3 8
2 7
3 4
1 8
2 8
3 7
2 10
1 6
6 11

Sample Output 4

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

Problem Statement

There are N points equally spaced on a circle, numbered 1,2,\dots,N clockwise.

You are given Q queries of the following form; process them in order.

• Draw the line segment connecting points A_i and B_i. However, if this segment intersects a segment that has already been drawn, do not draw it.

Here, it is guaranteed that the 2Q integers A_1,\ldots,A_Q,B_1,\ldots,B_Q are all distinct.

For each query, answer whether the segment was drawn.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 3\times 10^5
• 1 \leq A_i < B_i \leq N
• The 2Q integers A_1,\ldots,A_Q,B_1,\ldots,B_Q are pairwise distinct.
• All input values are integers.

Sample Input 1

8 3
1 5
2 7
3 4

Sample Output 1

Yes
No
Yes

By the queries, the segments are drawn as in the figure.

• In the 1-st query, the segment connecting points 1 and 5 is drawn.
• In the 2-nd query, the segment connecting points 2 and 7 is not drawn because it intersects the segment drawn in the 1-st query.
• In the 3-rd query, the segment connecting points 3 and 4 is drawn.

Sample Input 2

999999 4
123456 987654
888888 999999
1 3
2 777777

Sample Output 2

Yes
No
Yes
No