Problem Statement

In the figure shown in the image below, are the points numbered a and b directly connected by a line segment?

Constraints

• 1 \leq a \lt b \leq 10
• a and b are integers.

Sample Input 1

4 5

Sample Output 1

Yes

In the figure shown in the Problem Statement, the points numbered 4 and 5 are directly connected by a line segment.
Thus, Yes should be printed.

Sample Input 2

3 5

Sample Output 2

No

In the figure shown in the Problem Statement, the points numbered 3 and 5 are not directly connected by a line segment.
Thus, No should be printed.

Sample Input 3

1 10

Sample Output 3

Yes

Problem Statement

The number pi to the 100-th decimal place is

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679.

You are given an integer N between 1 and 100, inclusive.

Print the value of pi to the N-th decimal place.

More precisely, truncate the value of pi to N decimal places and print the result without removing the trailing 0s.

Constraints

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

Sample Input 1

2

Sample Output 1

3.14

Truncating the value of pi to 2 decimal places results in 3.14. Thus, you should print 3.14.

Sample Input 2

32

Sample Output 2

3.14159265358979323846264338327950

Do not remove the trailing 0s.

Sample Input 3

100

Sample Output 3

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

Problem Statement

KEYENCE has a culture of reporting things as they are, whether good or bad.
So we want to check whether the reported content is exactly the same as the original text.

You are given two strings S and T, consisting of lowercase English letters.
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Here, if the i-th character exists in only one of S and T, consider that the i-th characters are different.

More precisely, if S and T are not equal, print the smallest integer i satisfying one of the following conditions:

• 1\leq i\leq |S|, 1\leq i\leq |T|, and S_i\neq T_i.
• |S| < i \leq |T|.
• |T| < i \leq |S|.

Here, |S| and |T| denote the lengths of S and T, respectively, and S_i and T_i denote the i-th characters of S and T, respectively.

Constraints

• S and T are strings of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

abcde
abedc

Sample Output 1

3

We have S= abcde and T= abedc.
S and T have the same first and second characters, but differ at the third character, so print 3.

Sample Input 2

abcde
abcdefg

Sample Output 2

6

We have S= abcde and T= abcdefg.
S and T are equal up to the fifth character, but only T has a sixth character, so print 6.

Sample Input 3

keyence
keyence

Sample Output 3

0

S and T are equal, so print 0.

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

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

• Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

• 2 \leq N \leq 2\times 10^5
• (A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

• Initially, A=(3,4,1,2,5).
• The first operation swaps the first and third elements, making A=(1,4,3,2,5).
• The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

4
2 3
3 4
1 2
2 3

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

• 1 \leq |S| \leq 5\times 10^5
• S consists of lowercase English letters.
• T is obtained by inserting a lowercase English letter into S.

Sample Input 1

atcoder
atcorder

Sample Output 1

5

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

5

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

3

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

• If s_i is L, insert i to the immediate left of i-1 in A.
• If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

• 1\leq N \leq 5\times 10^5
• N is an integer.
• |S| = N
• s_i is L or R.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0

Problem Statement

Given is a string S consisting of K, E, Y.

How many strings are there that can be obtained with at most K swaps of two adjacent characters in S?

Constraints

• 2 \leq |S| \leq 30
• 0 \leq K \leq 10^9
• S consists of K, E, Y.

Sample Input 1

KEY
1

Sample Output 1

3

With at most one swap, there are three strings that can be obtained: KEY, EKY, KYE.

Sample Input 2

KKEE
2

Sample Output 2

4

With at most two swaps, there are four strings that can be obtained: KKEE, KEKE, EKKE, KEEK.

Sample Input 3

KKEEYY
1000000000

Sample Output 3

90

Problem Statement

Consider a binary tree with N vertices numbered 1, 2, \ldots, N. Here, a binary tree is a rooted tree where each vertex has at most two children. Specifically, each vertex in a binary tree has at most one left child and at most one right child.

Determine whether there exists a binary tree rooted at Vertex 1 satisfying the conditions below, and present such a tree if it exists.

• The depth-first traversal of the tree in pre-order is (P_1, P_2, \ldots, P_N).
• The depth-first traversal of the tree in in-order is (I_1, I_2, \ldots, I_N).

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is an integer.
• (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
• (I_1, I_2, \ldots, I_N) is a permutation of (1, 2, \ldots, N).

Sample Input 1

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

Sample Output 1

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

The binary tree rooted at Vertex 1 shown in the following image satisfies the conditions.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

No binary tree rooted at Vertex 1 satisfies the conditions, so -1 should be printed.