Problem Statement

You are given an integer sequence A=(A_1,A_2,A_3,A_4,A_5) obtained by permuting (1,2,3,4,5).

Determine whether A can be sorted in ascending order by performing exactly one operation of swapping two adjacent elements in A.

Constraints

• A is an integer sequence of length 5 obtained by permuting (1,2,3,4,5).

Sample Input 1

1 2 4 3 5

Sample Output 1

Yes

By swapping A_3 and A_4, A becomes (1,2,3,4,5), so it can be sorted in ascending order. Therefore, print Yes.

Sample Input 2

5 3 2 4 1

Sample Output 2

No

No matter what operation is performed, it is impossible to sort A in ascending order.

Sample Input 3

1 2 3 4 5

Sample Output 3

No

You must perform exactly one operation.

Sample Input 4

2 1 3 4 5

Sample Output 4

Yes

Problem Statement

You are given a string S consisting of lowercase English letters. The length of S is between 3 and 100, inclusive.

All characters but one of S are the same.

Find x such that the x-th character of S differs from all other characters.

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of two different lowercase English letters.
• All characters but one of S are the same.

Sample Input 1

yay

Sample Output 1

2

The second character of yay differs from the first and third characters.

Sample Input 2

egg

Sample Output 2

1

Sample Input 3

zzzzzwz

Sample Output 3

6

Problem Statement

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are N integers from 1 through N arranged in a line in ascending order.
Between them are M "レ" marks. The i-th "レ" mark is between the integer a_i and integer (a_i + 1).

You read each of the N integers once by the following procedure.

• Consider an undirected graph G with N vertices numbered 1 through N and M edges. The i-th edge connects vertex a_i and vertex (a_i+1).
• Repeat the following operation until there is no unread integer:
  • let x be the minimum unread integer. Choose the connected component C containing vertex x, and read all the numbers of the vertices contained in C in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

(In this case, N = 5, M = 3, and a = (1, 3, 4).)
Then, the order to read the integers is determined to be 2, 1, 5, 4, and 3, as follows:

• At first, the minimum unread integer is 1, and the connected component of G containing vertex 1 has vertices \lbrace 1, 2 \rbrace, so 2 and 1 are read in this order.
• Then, the minimum unread integer is 3, and the connected component of G containing vertex 3 has vertices \lbrace 3, 4, 5 \rbrace, so 5, 4, and 3 are read in this order.
• Now that all integers are read, terminate the procedure.

Given N, M, and (a_1, a_2, \dots, a_M), print the order to read the N integers.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq N - 1
• 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
• All values in the input are integers.

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

then the integers are read in the following order: 2, 1, 5, 4, and 3.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7

Problem Statement

You are given two grids, each with N rows and N columns, referred to as grid A and grid B.
Each cell in the grids contains a lowercase English letter.
The character at the i-th row and j-th column of grid A is A_{i, j}.
The character at the i-th row and j-th column of grid B is B_{i, j}.

The two grids differ in exactly one cell. That is, there exists exactly one pair (i, j) of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Find this (i, j).

Constraints

• 1 \leq N \leq 100
• A_{i, j} and B_{i, j} are all lowercase English letters.
• There exists exactly one pair (i, j) such that A_{i, j} \neq B_{i, j}.

Sample Input 1

3
abc
def
ghi
abc
bef
ghi

Sample Output 1

2 1

From A_{2, 1} = d and B_{2, 1} = b, we have A_{2, 1} \neq B_{2, 1}, so (i, j) = (2, 1) satisfies the condition in the problem statement.

Sample Input 2

1
f
q

Sample Output 2

1 1

Sample Input 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

Sample Output 3

5 9

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

Takahashi is initially in room R, and can move between rooms i - 1 and i only when door i is unlocked. Also, he can perform a switching operation on door i only when he is in room i - 1 or room i. When a switching operation is performed on door i, if the door is unlocked, it becomes locked, and if it is locked, it becomes unlocked.

Find the minimum number of switching operations needed to make all doors locked.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq R \leq N
• L_i \in \lbrace 0, 1 \rbrace
• All input values are integers.

Sample Input 1

6 3
1 0 0 1 0 0

Sample Output 1

6

Takahashi can make all doors locked with six switching operations by acting as follows:

• Move to room 2.
• Perform a switching operation on door 2 to lock door 2.
• Move to room 3.
• Perform a switching operation on door 4 to unlock door 4.
• Perform a switching operation on door 3 to lock door 3.
• Move to room 4.
• Perform a switching operation on door 4 to lock door 4.
• Move to room 5.
• Perform a switching operation on door 5 to lock door 5.
• Perform a switching operation on door 6 to lock door 6.

Sample Input 2

2 1
0 0

Sample Output 2

2

Sample Input 3

8 2
0 1 0 0 1 0 1 1

Sample Output 3

8

Problem Statement

Takahashi decided to hold a programming contest.

The contest consists of five problems: A, B, C, D, E, with scores a, b, c, d, e, respectively.

There are 31 participants, and all of them solved at least one problem.

More specifically, for every non-empty subsequence (not necessarily contiguous) of the string ABCDE, there is a participant named after that subsequence who solved the problems corresponding to the letters in their name and did not solve the other problems.

For example, participant A solved only problem A, and participant BCE solved problems B, C, and E.

Print the names of the participants in order of their obtained scores, from the largest to the smallest. The score obtained by a participant is the sum of the scores of the problems they solved.

If two participants obtained the same score, print the one whose name is lexicographically smaller first.

Constraints

• 100\leq a\leq b\leq c\leq d\leq e\leq 2718
• All input values are integers.

Sample Input 1

400 500 600 700 800

Sample Output 1

ABCDE
BCDE
ACDE
ABDE
ABCE
ABCD
CDE
BDE
ADE
BCE
ACE
BCD
ABE
ACD
ABD
ABC
DE
CE
BE
CD
AE
BD
AD
BC
AC
AB
E
D
C
B
A

The score of each participant is as follows:

For example, ADE and BCE obtained the same score, and ADE is lexicographically smaller, so print ADE before BCE.

Sample Input 2

800 800 900 900 1000

Sample Output 2

ABCDE
ACDE
BCDE
ABCE
ABDE
ABCD
CDE
ACE
ADE
BCE
BDE
ABE
ACD
BCD
ABC
ABD
CE
DE
AE
BE
CD
AC
AD
BC
BD
AB
E
C
D
A
B

Sample Input 3

128 256 512 1024 2048

Sample Output 3

ABCDE
BCDE
ACDE
CDE
ABDE
BDE
ADE
DE
ABCE
BCE
ACE
CE
ABE
BE
AE
E
ABCD
BCD
ACD
CD
ABD
BD
AD
D
ABC
BC
AC
C
AB
B
A

Problem Statement

There is a grid with H rows and W columns. We call the cell at the i-th row from the top (1\leq i\leq H) and j-th column from the left (1\leq j\leq W) as cell (i,j).

Initially, cell (i,j) is colored black if S_{i,j} is # and white if it is ..

Perform the following operation 10^{100} times:

• Let T be the set of cells that are colored white and have exactly one adjacent cell colored black. Color each cell in T black. Here, two cells (i_1,j_1) and (i_2,j_2) are adjacent if and only if |i_1-i_2|+|j_1-j_2|=1.

Find the number of cells that are colored black after all operations are completed.

Constraints

• 2\leq H,W
• HW\leq 3\times 10^5
• H and W are integers.
• S_{i,j} is # or ..

Sample Input 1

9 9
.........
.........
.........
.........
....#....
.........
.........
.........
.........

Sample Output 1

57

The grid changes as follows through the operations. (The number above represents the operation count. The first ten operations are displayed.)

Eventually, 57 cells are colored black.

Sample Input 2

2 2
..
..

Sample Output 2

0

Sample Input 3

10 10
..........
....#.....
#.......#.
......#...
.......#..
.....#....
..........
..........
..#...#...
.......#..

Sample Output 3

64

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.
Respond to the following Q queries in the order they are given.

The k-th query is given in the following format:

i_k x_k

• First, change A_{i_k} to x_k. This change will carry over to subsequent queries.
• Then, print the \rm{mex} of A.
  • The \rm{mex} of A is the smallest non-negative integer not contained in A.

Constraints

• All input values are integers.
• 1 \le N,Q \le 2 \times 10^5
• 0 \le A_i \le 10^9
• 1 \le i_k \le N
• 0 \le x_k \le 10^9

Sample Input 1

8 5
2 0 2 2 1 1 2 5
4 3
4 4
6 3
8 1000000000
2 1

Sample Output 1

4
3
6
5
0

Initially, the sequence A is (2,0,2,2,1,1,2,5).
This input gives you five queries.

• The first query changes A_4 to 3, making A=(2,0,2,3,1,1,2,5).
  • At this point, the \rm{mex} of A is 4.
• The second query changes A_4 to 4, making A=(2,0,2,4,1,1,2,5).
  • At this point, the \rm{mex} of A is 3.
• The third query changes A_6 to 3, making A=(2,0,2,4,1,3,2,5).
  • At this point, the \rm{mex} of A is 6.
• The fourth query changes A_8 to 1000000000, making A=(2,0,2,4,1,3,2,1000000000).
  • At this point, the \rm{mex} of A is 5.
• The fifth query changes A_2 to 1, making A=(2,1,2,4,1,3,2,1000000000).
  • At this point, the \rm{mex} of A is 0.

Problem Statement

In the nation of AtCoder, there are N cities numbered 1 to N, and M roads numbered 1 to M.
Road i connects cities A_i and B_i bidirectionally and has a length of C_i.

You are given Q queries to process in order. The queries are of the following two types.

• 1 i: Road i becomes closed.
• 2 x y: Print the shortest distance from city x to city y, using only roads that are not closed. If city y cannot be reached from city x, print -1 instead.

It is guaranteed that each test case contains at most 300 queries of the first type.

Constraints

• 2 \leq N \leq 300
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• All pairs (A_i, B_i) are distinct.
• 1 \leq C_i \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• In the queries of the first type, 1 \leq i \leq M.
• The road given in a query of the first type is not already closed at that time.
• The number of queries of the first type is at most 300.
• In the queries of the second type, 1 \leq x < y \leq N.
• All input values are integers.

Sample Input 1

3 3 5
1 2 5
1 3 10
2 3 6
2 1 3
1 2
2 1 3
1 1
2 1 3

Sample Output 1

10
11
-1

• In the first query, print the shortest distance from city 1 to city 3, which is 10.
• In the second query, road 2 becomes closed.
• In the third query, print the shortest distance from city 1 to city 3, which is 11.
• In the fourth query, road 1 becomes closed.
• In the fifth query, city 3 cannot be reached from city 1, so print -1.

Sample Input 2

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

Sample Output 2

-1
-1
-1