Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

In the AtCoder Kingdom, there are N castle walls numbered from 1 through N. There are also M turrets.

Turret i guards castle walls numbered from L_i through R_i.

When a turret is destroyed, the castle walls that were guarded by that turret are no longer guarded by that turret.

What is the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret?

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

10 4
1 6
4 5
5 10
7 10

Sample Output 1

1

If turret 1 is destroyed, no turret guards castle wall 3. Also, if no turrets are destroyed, all castle walls are guarded by some turret. Therefore, output 1.

Sample Input 2

5 2
1 2
3 4

Sample Output 2

0

Since no turret guards castle wall 5, there already exists a castle wall not guarded by any turret without destroying any turrets. Therefore, output 0.

Sample Input 3

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

Sample Output 3

3

Problem Statement

You are given a string S of length N consisting of 0 and 1.

A string T of length N consisting of 0 and 1 is a good string if and only if it satisfies the following condition:

• There is exactly one integer i such that 1 \leq i \leq N - 1 and the i-th and (i + 1)-th characters of T are the same.

For each i = 1,2,\ldots, N, you can choose whether or not to perform the following operation once:

• If the i-th character of S is 0, replace it with 1, and vice versa. The cost of this operation, if performed, is C_i.

Find the minimum total cost required to make S a good string.

Constraints

• 2 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 1 \leq C_i \leq 10^9
• N and C_i are integers.

Sample Input 1

5
00011
3 9 2 6 4

Sample Output 1

7

Performing the operation for i = 1, 5 and not performing it for i = 2, 3, 4 makes S = 10010, which is a good string. The cost incurred in this case is 7, and it is impossible to make S a good string for less than 7, so print 7.

Sample Input 2

4
1001
1 2 3 4

Sample Output 2

0

Sample Input 3

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

Sample Output 3

2286846953

Problem Statement

There are N squares called Square 1 though Square N. You start on Square 1.

Each of the squares from Square 1 through Square N-1 has a die on it. The die on Square i is labeled with the integers from 0 through A_i, each occurring with equal probability. (Die rolls are independent of each other.)

Until you reach Square N, you will repeat rolling a die on the square you are on. Here, if the die on Square x rolls the integer y, you go to Square x+y.

Find the expected value, modulo 998244353, of the number of times you roll a die.

Notes

It can be proved that the sought expected value is always a rational number. Additionally, if that value is represented \frac{P}{Q} using two coprime integers P and Q, there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N-i(1 \le i \le N-1)
• All values in input are integers.

Sample Input 1

3
1 1

Sample Output 1

4

The sought expected value is 4, so 4 should be printed.

Here is one possible scenario until reaching Square N:

• Roll 1 on Square 1, and go to Square 2.
• Roll 0 on Square 2, and stay there.
• Roll 1 on Square 2, and go to Square 3.

This scenario occurs with probability \frac{1}{8}.

Sample Input 2

5
3 1 2 1

Sample Output 2

332748122

Problem Statement

You are given a sequence of integers A=(A_1,\ldots,A_N). For a tree T with N vertices, define f(T) as follows:

• Let d_i be the degree of vertex i in T. Then, f(T)=\sum_{i=1}^N {d_i}^2 A_i.

Find the minimum possible value of f(T).

The constraints guarantee the answer to be less than 2^{63}.

Constraints

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

Sample Input 1

4
3 2 5 2

Sample Output 1

24

Consider a tree T with an edge connecting vertices 1 and 2, an edge connecting vertices 2 and 4, and an edge connecting vertices 4 and 3.

Then, f(T) = 1^2\times 3 + 2^2\times 2 + 1^2\times 5 + 2^2\times 2 = 24. It can be proven that this is the minimum value of f(T).

Sample Input 2

3
4 3 2

Sample Output 2

15

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

128