Problem Statement

You are given a string S of length N consisting of lowercase English letters.
If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No. (The order of a and b does not matter.)

Constraints

• 2 \leq N \leq 100
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3
abc

Sample Output 1

Yes

The string abc has a as the first character and b as the second character, which are adjacent. Thus, print Yes.

Sample Input 2

2
ba

Sample Output 2

Yes

The string ba has a as the second character and b as the first character, which are adjacent. (Note that the order of a and b does not matter.)

Sample Input 3

7
atcoder

Sample Output 3

No

Problem Statement

You are given an integer B.
If there exists a positive integer A such that A^A = B, print its value; otherwise, output -1.

Constraints

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

Sample Input 1

27

Sample Output 1

3

3^3 = 27, so print 3.

Sample Input 2

100

Sample Output 2

-1

There is no A such that A^A = B.

Sample Input 3

10000000000

Sample Output 3

10

Problem Statement

There is a 9\times 9 grid A, where each cell contains an integer between 1 and 9, inclusive.
Specifically, the cell at the i-th row from the top and j-th column from the left contains A_{i,j}.

If A satisfies all of the following conditions, print Yes. Otherwise, print No.

• For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.
• For each column of A, the nine cells in that column contain each integer from 1 to 9 exactly once.
• Divide the rows of A into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right. Each 3\times 3 grid obtained from A in this way contains each integer from 1 to 9 exactly once.

Constraints

• 1\leq A_{i,j}\leq 9
• All input values are integers.

Sample Input 1

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Sample Output 1

Yes

The grid A is shown below.

The grid A satisfies all three conditions, so print Yes.

Sample Input 2

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

Sample Output 2

No

The grid A is shown below.

For example, if you look at the top left 3\times 3 grid, you can see that the third condition is unsatisfied, so print No.

Sample Input 3

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6

Sample Output 3

No

The grid A is shown below.

For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.

Problem Statement

A pair of sequences of length M consisting of positive integers at most N, (S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M)), is said to be a good pair of sequences when (S, T) satisfies the following condition.

• There exists a sequence X = (X_1, X_2, \dots, X_N) of length N consisting of 0 and 1 that satisfies the following condition:
  • X_{S_i} \neq X_{T_i} for each i=1, 2, \dots, M.

You are given a pair of sequences of length M consisting of positive integers at most N: (A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M)). If (A, B) is a good pair of sequences, print Yes; otherwise, print No.

Constraints

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

Sample Input 1

3 2
1 2
2 3

Sample Output 1

Yes

If we set X=(0,1,0), then X is a sequence of length N consisting of 0 and 1 that satisfies X_{A_1} \neq X_{B_1} and X_{A_2} \neq X_{B_2}.
Thus, (A, B) satisfies the condition of being a good pair of sequences.

Sample Input 2

3 3
1 2 3
2 3 1

Sample Output 2

No

No sequence X satisfies the condition, so (A, B) is not a good pair of sequences.

Sample Input 3

10 1
1
1

Sample Output 3

No

Sample Input 4

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

Sample Output 4

Yes

Problem Statement

Takahashi participated in N contests and earned a performance P_i in the i-th contest.
He wants to choose some (at least one) contests from these and maximize his rating calculated from the results of those contests.

Find the maximum possible rating he can achieve by optimally choosing the contests.

Here, Takahashi's rating R is calculated as the following, where k is the number of chosen contests and (Q_1, Q_2, \ldots, Q_k) are the performances in the chosen contests in the order he participated:

Constraints

• 1\leq N\leq 5000
• 1\leq P_i\leq 5000
• All input values are integers.

Sample Input 1

3
1000 600 1200

Sample Output 1

256.735020470879931

If Takahashi chooses the first and third contests, his rating will be:

\displaystyle R=\frac{0.9\times 1000+ 1.0\times 1200}{0.9+1.0}-\frac{1200}{\sqrt{2}}=256.73502....

This is the maximum possible rating.

Sample Input 2

3
600 1000 1200

Sample Output 2

261.423219407873376

The rating is maximized when all the first, second, and third contests are selected.

Sample Input 3

1
100

Sample Output 3

-1100.000000000000000

The rating can also be negative.

Problem Statement

There are apple trees lined up on a number line, and N apples fall from the trees.
Specifically, for each 1\leq i\leq N, an apple falls at coordinate X_i at time T_i.

Takahashi has a basket with durability D and length W, and he can take the following action exactly once.

Choose positive integers S and L. He sets up the basket to cover the range L-0.5\leq x\leq L+W-0.5 at time S-0.5, and retrieves it at time S+D-0.5. He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.
Find the maximum number of apples that he can get.

Constraints

• 1 \leq N\leq 2\times 10^5
• 1 \leq D\leq 2\times 10^5
• 1 \leq W\leq 2\times 10^5
• 1 \leq T_i\leq 2\times 10^5
• 1 \leq X_i\leq 2\times 10^5
• All pairs (T_i,X_i) are different.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If Takahashi chooses S=3 and L=2, he will set up the basket to cover the range 1.5\leq x\leq 4.5 from time 2.5 to 6.5. Then, he gets the following five apples:

• The apple that falls at coordinate X_2=4 at time T_2=3
• The apple that falls at coordinate X_3=4 at time T_3=6
• The apple that falls at coordinate X_4=2 at time T_4=5
• The apple that falls at coordinate X_5=2 at time T_5=4
• The apple that falls at coordinate X_6=3 at time T_6=4

There is no way to get six or more apples, so print 5.

Problem Statement

The definition of a good pair of sequences in this problem is the same as in Problem D.

A pair of sequences of length M consisting of positive integers at most N, (S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M)), is said to be a good pair of sequences when (S, T) satisfies the following condition.

• There exists a sequence X = (X_1, X_2, \dots, X_N) of length N consisting of 0 and 1 that satisfies the following condition:
  • X_{S_i} \neq X_{T_i} for each i=1, 2, \dots, M.

Among the N^{2M} possible pairs of sequences of length M consisting of positive integers at most N, (A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M)), find the number, modulo 998244353, of those that are good pairs of sequences.

Constraints

• 1 \leq N \leq 30
• 1 \leq M \leq 10^9
• N and M are integers.

Sample Input 1

3 2

Sample Output 1

36

For example, if A=(1,2), B=(2,3), then (A, B) is a good pair of sequences. Indeed, if we set X=(0,1,0), then X is a sequence of length N consisting of 0 and 1 that satisfies X_{A_1} \neq X_{B_1} and X_{A_2} \neq X_{B_2}. Thus, (A, B) satisfies the condition of being a good pair of sequences.
There are a total of 36 good pairs of sequences, so print this number.

Sample Input 2

3 3

Sample Output 2

168

Sample Input 3

12 34

Sample Output 3

539029838

Sample Input 4

20 231104

Sample Output 4

966200489