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