Problem Statement

Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.

This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?

Constraints

• 1 \leq V,A,B,C \leq 10^5
• All values in input are integers.

Sample Input 1

25 10 11 12

Sample Output 1

T

Now, they have 25 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 15.
• Next, Takahashi's mother uses 11 milliliters, leaving 4.
• Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.

Sample Input 2

30 10 10 10

Sample Output 2

F

Now, they have 30 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 20.
• Next, Takahashi's mother uses 10 milliliters, leaving 10.
• Then, Takahashi uses 10 milliliters, leaving 0.
• Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.

Sample Input 3

100000 1 1 1

Sample Output 3

M

Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

• All participants who ranked A-th or higher get a T-shirt.
• Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

• All values in input are integers.
• 1 \le A < B \le 1000
• 1 \le C \le B-A
• 1 \le X \le 1000

Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.

Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.

Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

• N is an integer between 1 and 1000, inclusive.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

Problem Statement

There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:

• We can choose at most 3 different weights so that they have a total mass of n.

How many positive integers less than or equal to W are good integers?

Constraints

• 1 \leq N \leq 300
• 1 \leq W \leq 10^6
• 1 \leq A_i \leq 10^6
• All values in input are integers.

Sample Input 1

2 10
1 3

Sample Output 1

3

If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.

Sample Input 2

2 1
2 3

Sample Output 2

0

There are no good integers less than or equal to W.

Sample Input 3

4 12
3 3 3 3

Sample Output 3

3

There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.

Sample Input 4

7 251
202 20 5 1 4 2 100

Sample Output 4

48

Problem Statement

The programming contest World Tour Finals is underway, where N players are participating, and half of the competition time has passed. There are M problems in this contest, and the score A_i of problem i is a multiple of 100 between 500 and 2500, inclusive.

For each i = 1, \ldots, N, you are given a string S_i that indicates which problems player i has already solved. S_i is a string of length M consisting of o and x, where the j-th character of S_i is o if player i has already solved problem j, and x if they have not yet solved it. Here, none of the players have solved all the problems yet.

The total score of player i is calculated as the sum of the scores of the problems they have solved, plus a bonus score of i points.
For each i = 1, \ldots, N, answer the following question.

• At least how many of the problems that player i has not yet solved must player i solve to exceed all other players' current total scores?

Note that under the conditions in this statement and the constraints, it can be proved that player i can exceed all other players' current total scores by solving all the problems, so the answer is always defined.

Constraints

• 2\leq N\leq 100
• 1\leq M\leq 100
• 500\leq A_i\leq 2500
• A_i is a multiple of 100.
• S_i is a string of length M consisting of o and x.
• S_i contains at least one x.
• All numeric values in the input are integers.

Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The players' total scores at the halfway point of the competition time are 2001 points for player 1, 1502 points for player 2, and 1703 points for player 3.

Player 1 is already ahead of all other players' total scores without solving any more problems.

Player 2 can, for example, solve problem 4 to have a total score of 3502 points, which would exceed all other players' total scores.

Player 3 can also, for example, solve problem 4 to have a total score of 3703 points, which would exceed all other players' total scores.

Sample Input 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

Sample Output 2

1
1
1
1
0

Sample Input 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

Sample Output 3

7
6
5
4
3
2
0

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

Constraints

• 1 \le |S| \le 8
• S consists of lowercase English letters.
• There are at least K distinct strings that are permutations of S.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

Problem Statement

We have a horizontal cylinder. Given Q queries, process them in the given order.
Each query is of one of the following two types.

• 1 x c: Insert c balls, with a number x written on each of them, to the right end of the cylinder.
• 2 c: Take out the c leftmost balls contained in the cylinder and print the sum of the numbers written on the balls that have been taken out.

We assume that the balls do never change their order in the cylinder.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq 10^9
• Whenever a query of type 2 c is given, there are c or more balls in the cylinder.
• All values in input are integers.

Sample Input 1

4
1 2 3
2 2
1 3 4
2 3

Sample Output 1

4
8

• For the 1-st query, insert 3 balls, with a number 2 written on each of them, to the right end of the cylinder.
  The cylinder has now balls with numbers (2,2,2) written on them, from left to right.
• For the 2-nd query, take out the 2 leftmost balls contained in the cylinder.
  The numbers written on the balls taken out are 2,2, for a sum of 4, which should be printed. The cylinder has now a ball with a number (2) written on it, from left to right.
• For the 3-rd query, insert 4 balls, with a number 3 written on each of them, to the right end of the cylinder.
  The cylinder has now balls with numbers (2,3,3,3,3) written on them, from left to right.
• For the 4-th query, take out the 3 leftmost balls contained in the cylinder.
  The numbers written on the balls taken out are 2,3,3, for a sum of 8, which should be printed. The cylinder has now balls with numbers (3,3) written on them, from left to right.

Sample Input 2

2
1 1000000000 1000000000
2 1000000000

Sample Output 2

1000000000000000000

Sample Input 3

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output 3

There may be nothing you should print.

Problem Statement

A graph with (k+1) vertices and k edges is called a level-k\ (k\geq 2) star if and only if:

• it has a vertex that is connected to each of the other k vertices with an edge, and there are no other edges.

At first, Takahashi had a graph consisting of stars. He repeated the following operation until every pair of vertices in the graph was connected:

• choose two vertices in the graph. Here, the vertices must be disconnected, and their degrees must be both 1. Add an edge that connects the chosen two vertices.

He then arbitrarily assigned an integer from 1 through N to each of the vertices in the graph after the procedure. The resulting graph is a tree; we call it T. T has (N-1) edges, the i-th of which connects u_i and v_i.

Takahashi has now forgotten the number and levels of the stars that he initially had. Find them, given T.

Constraints

• 3\leq N\leq 2\times 10^5
• 1\leq u_i, v_i\leq N
• The given graph is an N-vertex tree obtained by the procedure in the problem statement.
• All values in the input are integers.

Sample Input 1

6
1 2
2 3
3 4
4 5
5 6

Sample Output 1

2 2

Two level-2 stars yield T, as the following figure shows:

Sample Input 2

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

Sample Output 2

2 2 2

Sample Input 3

20
8 3
8 18
2 19
8 20
9 17
19 7
8 7
14 12
2 15
14 10
2 13
2 16
2 1
9 5
10 15
14 6
2 4
2 11
5 12

Sample Output 3

2 3 4 7

Problem Statement

There are integer sequences A, B, C of length M each.

C is represented by integers x_1, \dots, x_N, y_1, \dots, y_N. The first y_1 terms of C are x_1, the subsequent y_2 terms are x_2, \ldots, the last y_N terms are x_N.

B is defined by B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M).

A is defined by A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M).

Find the maximum value among A_1, \dots, A_M.

You will be given T test cases to solve.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• The sum of N in a single file is at most 2 \times 10^5.
• 1 \leq M \leq 10^9
• |x_i| \leq 4 \, (1 \leq i \leq N)
• y_i \gt 0 \, (1 \leq i \leq N)
• \sum_{k = 1}^N y_k = M
• All values in input are integers.

Sample Input 1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

Sample Output 1

4
53910
2000000002000000000

In the first test case, we have:

• C = (-1, -1, 2, 2, 2, -3, -3)
• B = (-1, -2, 0, 2, 4, 1, -2)
• A = (-1, -3, -3, -1, 3, 4, 2)

Thus, the maximum value among A_1, \dots, A_M is 4.