Problem Statement

Given a length-3 string S consisting of uppercase English letters, print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Constraints

• S is a length-3 string consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

No

When S = ABC, S does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.

Sample Input 2

FAC

Sample Output 2

Yes

Sample Input 3

XYX

Sample Output 3

No

Problem Statement

Given a string S of length N consisting of lowercase English alphabets, print the last character of S.

Constraints

• N is an integer.
• 1 ≤ N ≤ 1000
• S is a string of length N consisting of lowercase English alphabets.

Sample Input 1

5
abcde

Sample Output 1

e

The last character of S = {}abcde is e, so e should be printed.

Sample Input 2

1
a

Sample Output 2

a

Problem Statement

There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.

Constraints

• 1 \leq K \leq N \leq 100
• K and N are integers.
• S_i is a string of length 10 consisting of lowercase English letters.
• S_i \neq S_j if i \neq j.

Sample Input 1

5 3
abc
aaaaa
xyz
a
def

Sample Output 1

aaaaa
abc
xyz

This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.

The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.

Sample Input 2

4 4
z
zyx
zzz
rbg

Sample Output 2

rbg
z
zyx
zzz

Sample Input 3

3 1
abc
arc
agc

Sample Output 3

abc

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

• 1 \leq N \leq 1000
• 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

3

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 3

7

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

• N is an integer.
• 2 \leq N \leq 2 \times 10^5
• S_i is a string consisting of lowercase English letters.
• |S_i| \geq 1
• \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

3

• S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
• S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
• S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

Problem Statement

There are N toys numbered from 1 to N, and N-1 boxes numbered from 1 to N-1. Toy i\ (1 \leq i \leq N) has a size of A_i, and box i\ (1 \leq i \leq N-1) has a size of B_i.

Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:

1. Choose an arbitrary positive integer x and purchase one box of size x.
2. Place each of the N toys into one of the N boxes (the N-1 existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy's size, and no box can contain two or more toys.

He wants to execute step 2 by purchasing a sufficiently large box in step 1, but larger boxes are more expensive, so he wants to purchase the smallest possible box.

Determine whether there exists a value of x such that he can execute step 2, and if it exists, find the minimum such x.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

4
5 2 3 7
6 2 8

Sample Output 1

3

Consider the case where x=3 (that is, he purchases a box of size 3 in step 1).

If the newly purchased box is called box 4, toys 1,\dots,4 have sizes of 5, 2, 3, and 7, respectively, and boxes 1,\dots,4 have sizes of 6, 2, 8, and 3, respectively. Thus, toy 1 can be placed in box 1, toy 2 in box 2, toy 3 in box 4, and toy 4 in box 3.

On the other hand, if x \leq 2, it is impossible to place all N toys into separate boxes. Therefore, the answer is 3.

Sample Input 2

4
3 7 2 5
8 1 6

Sample Output 2

-1

No matter what size of box is purchased in step 1, no toy can be placed in box 2, so it is impossible to execute step 2.

Sample Input 3

8
2 28 17 39 57 56 37 32
34 27 73 28 76 61 27

Sample Output 3

37

Problem Statement

For a positive integer N, let V_N be the integer formed by concatenating N exactly N times.
More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get V_N.
For example, V_3=333 and V_{10}=10101010101010101010.

Find the remainder when V_N is divided by 998244353.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

5

Sample Output 1

55555

The remainder when V_5=55555 is divided by 998244353 is 55555.

Sample Input 2

9

Sample Output 2

1755646

The remainder when V_9=999999999 is divided by 998244353 is 1755646.

Sample Input 3

10000000000

Sample Output 3

468086693

Note that the input may not fit into a 32-bit integer type.

Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Determine whether it is possible to make S identical to T by repeating the operation below any number of times (possibly zero). If it is possible, also find the minimum number of operations required.

• Choose two lowercase English letters x, y and replace every occurrence of x in S with y.

Constraints

• 1\leq N \leq 2\times 10^5
• N is an integer.
• Each of S and T is a string of length N, consisting of lowercase English letters.

Sample Input 1

6
afbfda
bkckbb

Sample Output 1

4

By performing the operation four times in the following way, you can make S identical to T:

1. Choose x= b and y= c. S becomes afcfda.
2. Choose x= a and y= b. S becomes bfcfdb.
3. Choose x= f and y= k. S becomes bkckdb.
4. Choose x= d and y= b. S becomes bkckbb, which is identical to T.

It cannot be done with fewer than four operations, so the minimum number of operations required is 4.

Sample Input 2

4
abac
abac

Sample Output 2

0

S and T are already identical, so no operations are required.

Sample Input 3

4
abac
abrc

Sample Output 3

-1

No matter how you repeat the operation, it is impossible to make S identical to T.

Sample Input 4

4
abac
bcba

Sample Output 4

4

Problem Statement

You are given a matrix A whose elements are non-negative integers. For a pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, let A_{i, j} denote the element at the i-th row and j-th column of A.

Let us perform the following procedure on A.

• First, replace each element of A that is 0 with an arbitrary positive integer (if multiple elements are 0, they may be replaced with different positive integers).

• Then, repeat performing one of the two operations below, which may be chosen each time, as many times as desired (possibly zero).

  • Choose a pair of integers (i, j) such that 1 \leq i \lt j \leq H and swap the i-th and j-th rows of A.
  • Choose a pair of integers (i, j) such that 1 \leq i \lt j \leq W and swap the i-th and j-th columns of A.

Determine whether A can be made to satisfy the following condition.

• A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W}.

• In other words, for every two pairs of integers (i, j) and (i', j') such that 1 \leq i, i' \leq H and 1 \leq j, j' \leq W, both of the following conditions are satisfied.

  • If i \lt i', then A_{i, j} \leq A_{i', j'}.
  • If i = i' and j \lt j', then A_{i, j} \leq A_{i', j'}.

Constraints

• 2 \leq H, W
• H \times W \leq 10^6
• 0 \leq A_{i, j} \leq H \times W
• All values in the input are integers.

Sample Input 1

3 3
9 6 0
0 4 0
3 0 3

Sample Output 1

Yes

One can perform the operations as follows to make A satisfy the condition in the problem statement, so you should print Yes.

• First, replace the elements of A that are 0, as shown below:

9 6 8
5 4 4
3 1 3

• Swap the second and third columns. Then, A becomes:

9 8 6
5 4 4
3 3 1

• Swap the first and third rows. Then, A becomes:

3 3 1
5 4 4
9 8 6

• Swap the first and third columns. Then, A becomes the following and satisfies the condition in the problem statement.

1 3 3
4 4 5
6 8 9

Sample Input 2

2 2
2 1
1 2

Sample Output 2

No

There is no way to perform the operations to make A satisfy the condition in the problem statement, so you should print No.