Problem Statement

Takahashi decided to make takoyaki (octopus balls) and serve it to Snuke. Takahashi instructed Snuke to raise only his left hand if he wants to eat takoyaki, and only his right hand otherwise.

You are given the information about which hand Snuke is raising as two integers L and R. He is raising his left hand if and only if L = 1, and raising his right hand if and only if R = 1. He might not follow the instructions and could raise both hands or not raise any hand at all.

If Snuke is raising only one hand, print Yes if he wants to eat takoyaki, and No if he does not. If he is raising both hands or not raising any hand, print Invalid.

Assume that if Snuke is raising only one hand, he is always following the instructions.

Constraints

• Each of L and R is 0 or 1.

Sample Input 1

1 0

Sample Output 1

Yes

Snuke wants to eat takoyaki, so he is raising only his left hand.

Sample Input 2

1 1

Sample Output 2

Invalid

Snuke is raising both hands.

Problem Statement

You are given a string S consisting of A, B, and C. S is guaranteed to contain all of A, B, and C.

If the characters of S are checked one by one from the left, how many characters will have been checked when the following condition is satisfied for the first time?

• All of A, B, and C have appeared at least once.

Constraints

• 3 \leq N \leq 100
• S is a string of length N consisting of A, B, and C.
• S contains all of A, B, and C.

Sample Input 1

5
ACABB

Sample Output 1

4

In the first four characters from the left, A, B, and C appear twice, once, and once, respectively, satisfying the condition.
The condition is not satisfied by checking three or fewer characters, so the answer is 4.

Sample Input 2

4
CABC

Sample Output 2

3

In the first three characters from the left, each of A, B, and C appears once, satisfying the condition.

Sample Input 3

30
AABABBBABABBABABCABACAABCBACCA

Sample Output 3

17

Problem Statement

There are N people numbered Person 1, Person 2, \dots, and Person N. Person i has a family name s_i and a given name t_i.

Consider giving a nickname to each of the N people. Person i's nickname a_i should satisfy all the conditions below.

• a_i coincides with Person i's family name or given name. In other words, a_i = s_i and/or a_i = t_i holds.
• a_i does not coincide with the family name and the given name of any other person. In other words, for all integer j such that 1 \leq j \leq N and i \neq j, it holds that a_i \neq s_j and a_i \neq t_j.

Is it possible to give nicknames to all the N people? If it is possible, print Yes; otherwise, print No.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• s_i and t_i are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English alphabets.

Sample Input 1

3
tanaka taro
tanaka jiro
suzuki hanako

Sample Output 1

Yes

The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 = taro, a_2 = jiro, a_3 = hanako. (a_3 may be suzuki, too.)
However, note that we cannot let a_1 = tanaka, which violates the second condition of nicknames, since Person 2's family name s_2 is tanaka too.

Sample Input 2

3
aaa bbb
xxx aaa
bbb yyy

Sample Output 2

No

There is no way to give nicknames satisfying the conditions in the Problem Statement.

Sample Input 3

2
tanaka taro
tanaka taro

Sample Output 3

No

There may be a pair of people with the same family name and the same given name.

Sample Input 4

3
takahashi chokudai
aoki kensho
snu ke

Sample Output 4

Yes

We can let a_1 = chokudai, a_2 = kensho, and a_3 = ke.

Problem Statement

On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.

For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.

You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.

Constraints

• S consists of lowercase English letters.
• The length of S is between 1 and 1000 (inclusive).

Sample Input 1

aaba

Sample Output 1

aaab
baaa

By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.

Sample Input 2

z

Sample Output 2

z
z

Any sequence of operations results in z.

Sample Input 3

abracadabra

Sample Output 3

aabracadabr
racadabraab

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N).

Find the minimum possible sum of all elements of A after performing the following operation exactly K times.

• Choose an integer x. For each i such that A_i = x, replace the value of A_i with 0.

Constraints

• 1 \leq K \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

6 2
7 2 7 2 2 9

Sample Output 1

6

Initially, A = (7, 2, 7, 2, 2, 9).

Performing the operation with x = 9 gives A = (7, 2, 7, 2, 2, 0).

Next, performing the operation with x = 7 gives A = (0, 2, 0, 2, 2, 0).

At this point, the sum of all elements of A is 0 + 2 + 0 + 2 + 2 + 0 = 6.

Sample Input 2

8 6
1 2 3 4 1 2 3 4

Sample Output 2

0

Sample Input 3

10 2
3 3 4 1 1 3 3 1 5 1

Sample Output 3

8

Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

• For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• (p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
• All values in input are integers.

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

• For i = 1, we have p_i = 2, q_2 = 1.
• For i = 2, we have p_i = 3, q_3 = 2.
• For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

Problem Statement

A superman, Takahashi, is about to jump off the roof of a building to help a person in trouble on the ground. Takahashi's planet has a constant value g that represents the strength of gravity, and the time it takes for him to reach the ground after starting to fall is \frac{A}{\sqrt{g}}.

It is now time 0, and g = 1. Takahashi will perform the following operation as many times as he wants (possibly zero).

• Use a superpower to increase the value of g by 1. This takes a time of B.

Then, he will jump off the building. After starting to fall, he cannot change the value of g. Additionally, we only consider the time it takes to perform the operation and fall.

Find the earliest time Takahashi can reach the ground.

Constraints

• 1 \leq A \leq 10^{18}
• 1 \leq B \leq 10^{18}
• All values in the input are integers.

Sample Input 1

10 1

Sample Output 1

7.7735026919

• If he performs the operation zero times, he will reach the ground at time 1\times 0+\frac{10}{\sqrt{1}} = 10.
• If he performs the operation once, he will reach the ground at time 1\times 1+\frac{10}{\sqrt{2}} \fallingdotseq 8.07.
• If he performs the operation twice, he will reach the ground at time 1\times 2+\frac{10}{\sqrt{3}} \fallingdotseq 7.77.
• If he performs the operation three times, he will reach the ground at time 1\times 3+\frac{10}{\sqrt{4}} = 8.

Performing the operation four or more times will only delay the time to reach the ground. Therefore, it is optimal to perform the operation twice before jumping off, and the answer is 2+\frac{10}{\sqrt{3}}.

Sample Input 2

5 10

Sample Output 2

5.0000000000

It is optimal not to perform the operation at all.

Sample Input 3

1000000000000000000 100

Sample Output 3

8772053214538.5976562500

Problem Statement

There are N people divided into three teams.

The people are numbered 1, 2, \ldots, N, and the teams are numbered 1, 2, 3. Currently, person i belongs to team A_i.

Each person has a value called strength; person i has a strength of B_i. The strength of a team is defined as the sum of the strengths of its members.

Determine whether it is possible for zero or more people to switch teams so that all teams have equal strength. If it is possible, find the minimum number of people who need to switch teams to achieve this.

You cannot create new teams other than teams 1, 2, 3.

Constraints

• 3 \leq N \leq 100
• A_i \in \lbrace 1, 2, 3 \rbrace
• For each x \in \lbrace 1, 2, 3 \rbrace, there exists some i with A_i = x.
• 1 \leq B_i
• \displaystyle\sum_{i = 1}^{N} B_i \leq 1500
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

If person 1 switches to team 3 and person 4 switches to team 2, all teams will have a strength of 8.

Sample Input 2

4
1 1
1 2
2 3
3 4

Sample Output 2

-1

Sample Input 3

3
1 1
2 1
3 1

Sample Output 3

0

Sample Input 4

12
2 5
1 4
3 3
2 3
3 9
1 2
2 2
3 9
2 6
1 9
1 1
3 1

Sample Output 4

3

Problem Statement

Given is a string S. How many different strings can be obtained as a permutation of a non-empty, not necessarily contiguous subsequence of S?

Since the count can be enormous, print it modulo 998244353.

Constraints

• S is a string of length 1 and 5000 (inclusive) consisting of lowercase English letters.

Sample Input 1

aab

Sample Output 1

8

There are 8 different strings that can be obtained as a permutation of a subsequence of S: a, b, aa, ab, ba, aab, aba, baa.

Sample Input 2

aaa

Sample Output 2

3

Sample Input 3

abcdefghijklmnopqrstuvwxyz

Sample Output 3

149621752

Be sure to print the count modulo 998244353.