Problem Statement

You are given an odd-length string S consisting of lowercase English letters.

Print the central character of S.

Constraints

• S is an odd-length string consisting of lowercase English letters.
• The length of S is between 1 and 99 (inclusive).

Sample Input 1

atcoder

Sample Output 1

o

The central character of atcoder is o.

Sample Input 2

a

Sample Output 2

a

Problem Statement

Takahashi and Aoki decided to jog.
Takahashi repeats the following: "walk at B meters a second for A seconds and take a rest for C seconds."
Aoki repeats the following: "walk at E meters a second for D seconds and take a rest for F seconds."
When X seconds have passed since they simultaneously started to jog, which of Takahashi and Aoki goes ahead?

Constraints

• 1 \leq A, B, C, D, E, F, X \leq 100
• All values in input are integers.

Sample Input 1

4 3 3 6 2 5 10

Sample Output 1

Takahashi

During the first 10 seconds after they started to jog, they move as follows.

• Takahashi walks for 4 seconds, takes a rest for 3 seconds, and walks again for 3 seconds. As a result, he advances a total of (4 + 3) \times 3 = 21 meters.
• Aoki walks for 6 seconds and takes a rest for 4 seconds. As a result, he advances a total of 6 \times 2 = 12 meters.

Since Takahashi goes ahead, Takahashi should be printed.

Sample Input 2

3 1 4 1 5 9 2

Sample Output 2

Aoki

Sample Input 3

1 1 1 1 1 1 1

Sample Output 3

Draw

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N) of length N and a positive integer M.

Your goal is to make the following condition false by performing this operation between 0 and N times (inclusive): remove the last element of A.

• Condition: A contains every integer from 1 through M.

Find the minimum number of operations required.

Under the constraints of this problem, it can be proved that it is always possible to make the condition false by performing the operation between 0 and N times.

Constraints

• 1 \le M \le N \le 100
• 1 \le A_i \le M
• All input values are integers.

Sample Input 1

5 3
3 2 3 1 2

Sample Output 1

2

Initially, A = (3,2,3,1,2). Since A contains every integer from 1 through 3, the condition holds.

If you perform the operation once, A = (3,2,3,1). The condition still holds.

If you perform the operation once more, A = (3,2,3). The integer 1 is missing, so the condition no longer holds.

Therefore, the minimum required number of operations is 2.

Sample Input 2

4 3
1 3 1 3

Sample Output 2

0

Since A initially lacks the integer 2, the condition is already false, so no operation is needed.

Sample Input 3

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

Sample Output 3

6

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

• choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

• Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
• S and T have the same length.

Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.

Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.

Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

• Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

• 1\leq N \leq 10^5
• 1 \leq A_j \leq N
• i occurs in A exactly three times, for each i=1,2,\dots,N.
• All input values are integers.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

• 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
• 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
• 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

4
2 3 4 3 4 1 3 1 1 4 2 2

Sample Output 3

3 4 1 2

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

For each i=1,\ldots,N, solve the following problem.

Problem: Find the sum of all elements in A that are greater than A_i.

Constraints

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

Sample Input 1

5
1 4 1 4 2

Sample Output 1

10 0 10 0 8

• For i=1, the sum of elements greater than A_1=1 is 4+4+2=10.
• For i=2, the sum of elements greater than A_2=4 is 0.
• For i=3, the sum of elements greater than A_3=1 is 4+4+2=10.
• For i=4, the sum of elements greater than A_4=4 is 0.
• For i=5, the sum of elements greater than A_5=2 is 4+4=8.

Sample Input 2

10
31 42 59 26 53 58 97 93 23 54

Sample Output 2

456 414 190 487 361 249 0 97 513 307

Sample Input 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Problem Statement

Takahashi will toss a coin N times. He also has a counter, which initially shows 0.

Depending on the result of the i-th coin toss, the following happens:

• If it heads: Takahashi increases the counter's value by 1 and receives X_i yen (Japanese currency).
• If it tails: he resets the counter's value to 0, without receiving money.

Additionally, there are M kinds of streak bonuses. The i-th kind of streak bonus awards Y_i yen each time the counter shows C_i.

Find the maximum amount of money that Takahashi can receive.

Constraints

• 1\leq M\leq N\leq 5000
• 1\leq X_i\leq 10^9
• 1\leq C_i\leq N
• 1\leq Y_i\leq 10^9
• C_1,C_2,\ldots,C_M are all different.
• All values in input are integers.

Sample Input 1

6 3
2 7 1 8 2 8
2 10
3 1
5 5

Sample Output 1

48

If he gets head, head, tail, head, head, head, in this order, the following amounts of money are awarded.

• In the 1-st coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 2 yen.
• In the 2-nd coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 7 yen. Additionally, get 10 yen as a streak bonus.
• In the 3-rd coin toss, the coin tails. Change the counter's value from 2 to 0.
• In the 4-th coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 8 yen.
• In the 5-th coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 2 yen. Additionally, get 10 yen as a streak bonus.
• In the 6-th coin toss, the coin heads. Change the counter's value from 2 to 3 and receive 8 yen. Additionally, get 1 yen as a streak bonus.

In this case, Takahashi receives 2+(7+10)+0+8+(2+10)+(8+1)=48 yen in total, which is the maximum possible.
Note that streak bonuses are awarded any number of times each time the counter shows C_i.
As a side note, if he gets head in all 6 coin tosses, he only receives 2+(7+10)+(1+1)+8+(2+5)+8=44 yen, which is not the maximum.

Sample Input 2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

Sample Output 2

5000000000

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

Problem Statement

There are N sticks in a bag, with lengths A_1,\ldots,A_N.

You repeat the following operation K times.

• Take out any one of the longest sticks in the bag, split it into two equal halves, and put the two sticks back into the bag.

After K operations, among the N+K sticks in the bag, find the length of the X-th longest one.

You are given T test cases; answer each of them.

Constraints

• 1 \leq T \leq 10^5
• For each test case:
  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq K \leq 10^9
  • 1 \leq X \leq N+K
• The sum of N over all test cases does not exceed 10^5.
• All input values are integers.

Sample Input 1

2
3 4 5
40 20 30
10 100 50
1 2 3 4 5 6 7 8 9 10

Sample Output 1

10.00000000000000000000
0.50000000000000000000

In the 1-st test case, initially the bag contains 3 sticks of lengths 20,30,40. The operations proceed as follows.

• Take out the stick of length 40 from the bag, split it into two sticks of length 20, and put them back. The stick lengths in the bag become 20,20,20,30.
• Take out the stick of length 30 from the bag, split it into two sticks of length 15, and put them back. The stick lengths in the bag become 15,15,20,20,20.
• Take out a stick of length 20 from the bag, split it into two sticks of length 10, and put them back. The stick lengths in the bag become 10,10,15,15,20,20.
• Take out a stick of length 20 from the bag, split it into two sticks of length 10, and put them back. The stick lengths in the bag become 10,10,10,10,15,15,20.

After the operations, the 5-th longest stick has length 10.

Problem Statement

We have N dice. For each i = 1, 2, \ldots, N, when the i-th die is thrown, it shows a random integer between 1 and A_i, inclusive, with equal probability.

Find the probability, modulo 998244353, that the following condition is satisfied when the N dice are thrown simultaneously.

There is a way to choose some (possibly all) of the N dice so that the sum of their results is 10.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^6
• All input values are integers.

Sample Input 1

4
1 7 2 9

Sample Output 1

942786334

For instance, if the first, second, third, and fourth dice show 1, 3, 2, and 7, respectively, these results satisfy the condition. In fact, if the second and fourth dice are chosen, the sum of their results is 3 + 7 = 10. Alternatively, if the first, third, and fourth dice are chosen, the sum of their results is 1 + 2 + 7 = 10.

On the other hand, if the first, second, third, and fourth dice show 1, 6, 1, and 5, respectively, there is no way to choose some of them so that the sum of their results is 10, so the condition is not satisfied.

In this sample input, the probability of the results of the N dice satisfying the condition is \frac{11}{18}. Thus, print this value modulo 998244353, that is, 942786334.

Sample Input 2

7
1 10 100 1000 10000 100000 1000000

Sample Output 2

996117877