Problem Statement

There is a mysterious button. When you press this button, you receive one candy, unless less than C seconds have elapsed since you last received a candy.

Takahashi decided to press this button N times. He will press the button for the i-th time T_i seconds from now.

How many candies will he receive?

Constraints

• 1 \leq N \leq 100
• 1 \leq C \leq 1000
• 0 \leq T_1 < T_2 < \dots < T_N \leq 1000
• All input values are integers.

Sample Input 1

6 5
1 3 7 8 10 12

Sample Output 1

3

Takahashi will press the button six times.

• 1st press (1 second from now): You always receive a candy when pressing the button for the first time.
• 2nd press (3 seconds from now): 3 - 1 = 2 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
• 3rd press (7 seconds from now): 7 - 1 = 6 \geq C seconds have elapsed since he last received a candy, so he receives a candy.
• 4th press (8 seconds from now): 8 - 7 = 1 < C second has elapsed since he last received a candy, so he does not receive a candy.
• 5th press (10 seconds from now): 10 - 7 = 3 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
• 6th press (12 seconds from now): 12 - 7 = 5 \geq C seconds have elapsed since he last received a candy, so he receives a candy.

Therefore, he receives three candies.

Sample Input 2

3 2
0 2 4

Sample Output 2

3

Sample Input 3

10 3
0 3 4 6 9 12 15 17 19 20

Sample Output 3

7

Problem Statement

Note: This problem has almost the same setting as Problem F. Only the parts in bold in the main text and constraints differ.

You are holding a ring with both hands. This ring consists of N\ (N \geq 3) parts numbered 1,2,\dots,N, where parts i and i+1 (1 \leq i \leq N-1) are adjacent, and parts 1 and N are also adjacent.

Initially, your left hand is holding part 1, and your right hand is holding part 2. In one operation, you can do the following:

• Move one of your hands to an adjacent part of the part it is currently holding. However, you can do this only if the other hand is not on the destination part.

The following figure shows the initial state and examples of operations that can and cannot be made from there. The number written on each part of the ring represents the part number, and the circles labeled L and R represent your left and right hands, respectively.

You need to follow Q instructions given to you in order. The i-th (1 \leq i \leq Q) instruction is represented by a character H_i and an integer T_i, meaning the following:

• Perform some number of operations (possibly zero) so that your left hand (if H_i is L) or your right hand (if H_i is R) is holding part T_i. Here, you must not move the other hand not specified by H_i.

It is guaranteed that only achievable instructions are given.

Find the minimum total number of operations required to follow all the instructions.

Constraints

• 3 \leq N \leq 100
• 1 \leq Q \leq 100
• H_i is L or R.
• 1 \leq T_i \leq N
• N, Q, and T_i are integers.
• Only achievable instructions are given (see the problem statement for details).

Sample Input 1

6 3
R 4
L 5
R 6

Sample Output 1

8

By performing the following operations, you can follow all Q instructions in order.

1. Move your right hand as part 2 \rightarrow 3 \rightarrow 4 to follow the first instruction.
2. Move your left hand as part 1 \rightarrow 6 \rightarrow 5 to follow the second instruction.
3. Move your right hand as part 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 6 to follow the third instruction.

In this case, the total number of operations is 2+2+4=8, which is the minimum. (Note that when following the third instruction, you cannot move your right hand as part 4 \rightarrow 5 \rightarrow 6.)

Sample Input 2

100 2
L 1
R 2

Sample Output 2

0

There are cases where you can follow the instructions without performing any operations.

Sample Input 3

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

Sample Output 3

92

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

There is a simple directed graph with N vertices numbered from 1 to N and M edges. The i-th edge (1 \leq i \leq M) is a directed edge from vertex a_i to vertex b_i.
Determine whether there exists a cycle that contains vertex 1, and if it exists, find the minimum number of edges among such cycles.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq \min \left( \frac{N(N-1)}{2},\ 2 \times 10^5 \right)
• 1 \leq a_i \leq N
• 1 \leq b_i \leq N
• a_i \neq b_i
• (a_i, b_i) \neq (a_j, b_j) and (a_i, b_i) \neq (b_j, a_j), if i \neq j.
• All input values are integers.

Sample Input 1

3 3
1 2
2 3
3 1

Sample Output 1

3

Vertex 1 \to vertex 2 \to vertex 3 \to vertex 1 is a cycle with three edges, and this is the only cycle that contains vertex 1.

Sample Input 2

3 2
1 2
2 3

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

4

Problem Statement

You are given sequences of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
Let S be a subset of \lbrace1, 2, \dots, N\rbrace of size K. Here, find the minimum possible value of the following expression:

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

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^6
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
3 2
3 7 6
9 2 4
5 3
6 4 1 5 9
8 6 5 1 7
10 6
61 95 61 57 69 49 46 47 14 43
39 79 48 92 90 76 30 16 30 94

Sample Output 1

42
60
14579

In the first test case, for S = \{2, 3\}, the value of the expression is 7 \times (2 + 4) = 42, which is the minimum.

Problem Statement

Note: This problem has almost the same setting as Problem B. Only the parts in bold in the main text and constraints differ.

You are holding a ring with both hands. This ring consists of N\ (N \geq 3) parts numbered 1,2,\dots,N, where parts i and i+1 (1 \leq i \leq N-1) are adjacent, and parts 1 and N are also adjacent.

Initially, your left hand is holding part 1, and your right hand is holding part 2. In one operation, you can do the following:

• Move one of your hands to an adjacent part of the part it is currently holding. However, you can do this only if the other hand is not on the destination part.

The following figure shows the initial state and examples of operations that can and cannot be made from there. The number written on each part of the ring represents the part number, and the circles labeled L and R represent your left and right hands, respectively.

You need to follow Q instructions given to you in order. The i-th (1 \leq i \leq Q) instruction is represented by a character H_i and an integer T_i, meaning the following:

• Perform some number of operations (possibly zero) so that your left hand (if H_i is L) or your right hand (if H_i is R) is holding part T_i. Here, you may move the other hand not specified by H_i.

Under the settings and constraints of this problem, it can be proved that any instructions are achievable.

Find the minimum total number of operations required to follow all the instructions.

Constraints

• 3\leq N \leq 3000
• 1\leq Q \leq 3000
• H_i is L or R.
• 1 \leq T_i \leq N
• N, Q, and T_i are integers.

Sample Input 1

6 3
R 4
L 5
R 5

Sample Output 1

6

By performing the following operations, you can follow all Q instructions in order.

1. Move your right hand as part 2 \rightarrow 3 \rightarrow 4 to follow the first instruction.
2. Move your left hand as part 1 \rightarrow 6 \rightarrow 5 to follow the second instruction.
3. Move your left hand as part 5 \rightarrow 6, then move your right hand as part 4 \rightarrow 5 to follow the third instruction.

In this case, the total number of operations is 2+2+1+1=6, which is the minimum.

Sample Input 2

100 2
L 1
R 2

Sample Output 2

0

There are cases where you can follow the instructions without performing any operations.

Sample Input 3

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

Sample Output 3

58

Problem Statement

There is a rooted tree with N + 1 vertices numbered from 0 to N. Vertex 0 is the root, and the parent of vertex i is vertex p_i.
One of the vertices among vertex 1, vertex 2, ..., vertex N hides a treasure. The probability that the treasure is at vertex i is \frac{a_i}{\sum_{j=1}^N a_j}. Also, each vertex is in one of the two states: "searched" and "unsearched". Initially, vertex 0 is searched, and all other vertices are unsearched.
Until the vertex containing the treasure becomes searched, you perform the following operation:

• Choose an unsearched vertex whose parent is searched, and mark it as searched.

Find the expected number of operations required when you act to minimize the expected number of operations, modulo 998244353.

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

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 0 \leq p_i < i
• 1 \leq a_i
• \sum_{i=1}^N a_i \leq 10^8
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
3
0 0 1
1 2 3
5
0 1 0 0 0
8 6 5 1 7
10
0 1 1 3 3 1 4 7 5 4
43 39 79 48 92 90 76 30 16 30

Sample Output 1

166374061
295776107
680203339

In the first test case, the expected number of operations is \frac{13}{6}.