Problem Statement

In Takahashi's garden, there are flower pots arranged in N steps like a staircase.

Each flower pot initially contains water, and the i-th flower pot contains A_i milliliters of water. Due to the staircase arrangement, the i-th flower pot is positioned higher than the (i + 1)-th flower pot (the N-th flower pot is at the lowest position, and beyond it is a drain).

When Takahashi exposes a flower pot to sunlight, part of the water evaporates and the rest flows down to the flower pot on the step below. Specifically, when sunlight is applied to the i-th flower pot, the following occurs:

• B_i milliliters of the water in that flower pot evaporates and disappears (if the water is less than B_i milliliters, all the water evaporates)
• All the water remaining after evaporation flows down to the flower pot on the step below (if i < N, it flows to the (i + 1)-th flower pot; if i = N, it flows into the drain and disappears)

Takahashi performs Q operations in order. In the j-th operation, he exposes the C_j-th flower pot to sunlight.

After all operations are completed, determine the amount of water remaining in each flower pot.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq B_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq C_j \leq N (1 \leq j \leq Q)
• All inputs are integers

Sample Input 1

3 2
10 5 3
3 2 4
1 2

Sample Output 1

0 0 13

Sample Input 2

5 6
100 50 30 20 10
20 10 15 5 8
1 2 3 4 5 1

Sample Output 2

0 0 0 0 0

Sample Input 3

7 10
1000000000 500000000 300000000 200000000 100000000 50000000 25000000
100000000 200000000 150000000 80000000 60000000 30000000 20000000
1 1 2 2 3 3 4 5 6 7

Sample Output 3

0 0 0 0 0 0 0

Problem Statement

Takahashi is hiking along a mountain trail. There are N points lined up in a row along the trail, and the elevation of the i-th point (1 \leq i \leq N) is A_i.

Takahashi calls a contiguous interval of one or more points an "uphill" if the elevations are non-decreasing. That is, an interval from the l-th to the r-th point (1 \leq l \leq r \leq N) is an "uphill" if A_i \leq A_{i+1} holds for all l \leq i \leq r-1. In particular, an interval consisting of only one point (l = r) is also an "uphill".

Find the "uphill" that contains the maximum number of points along this mountain trail, and output that number of points.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• All inputs are integers.

Sample Input 1

6
1
2
2
1
3
4

Sample Output 1

3

Sample Input 2

5
9
7
5
3
1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

5

Sample Input 4

30
8
9
9
10
7
7
8
12
12
13
5
6
7
8
9
3
3
4
4
4
10
11
2
2
2
3
1
5
6
7

Sample Output 4

7

Sample Input 5

1
1000000000

Sample Output 5

1

Problem Statement

Takahashi works in the HR department of a company. The company has N employees, and the organization has a tree structure.

Employee 1 is the president (the top of the organization), and the direct supervisor of each employee i (2 \leq i \leq N) is employee P_i.

Takahashi needs to assign a positive integer value called a "salary rank" to each employee. However, the following conditions must be satisfied:

• The salary rank of the president (employee 1) is 1.
• The salary rank of each employee is greater than or equal to the salary rank of their direct supervisor.
• Each employee i has an "upper rank limit" U_i, and the salary rank of employee i must be at most U_i.

Takahashi wants to maximize the total salary rank of all employees.

If a valid assignment of salary ranks satisfying the conditions exists, find the maximum total of all salary ranks. If no valid assignment exists, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq U_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_i < i (2 \leq i \leq N)
• All inputs are integers.

Sample Input 1

5
3
1 4
1 2
2 5
2 4

Sample Output 1

16

Sample Input 2

4
5
1 3
1 0
2 4

Sample Output 2

-1

Sample Input 3

15
10
1 6
1 12
2 8
2 3
3 15
3 7
4 9
4 5
5 4
6 20
6 11
7 13
7 2
10 6

Sample Output 3

97

Sample Input 4

30
100
1 50
1 80
2 45
2 60
3 90
3 30
4 55
4 25
5 70
5 65
6 95
6 40
7 35
7 85
8 20
8 75
9 15
9 1000000000
10 10
10 68
11 72
11 58
12 99
12 33
13 44
13 88
14 22
14 77
15 66

Sample Output 4

1000001124

Sample Input 5

1
1

Sample Output 5

1

Problem Statement

Takahashi is trying to distribute K balls into N boxes. The boxes are numbered Box 1, Box 2, \ldots, Box N from left to right, and the balls are numbered Ball 1, Ball 2, \ldots, Ball K. The boxes are distinguishable from each other, and the balls are distinguishable from each other.

The distribution must follow these rules:

1. Every ball must be placed in exactly one box, and each ball is placed in exactly one box.
2. Each box must contain at least one ball (no box may be empty).
3. Additionally, M constraints are given. The j-th constraint (1 \leq j \leq M) states that "Ball U_j and Ball V_j must be placed in the same box."

In the constraints of Rule 3, the "must be in the same box" relationship is applied transitively. That is, if there is a constraint that Ball A and Ball B must be in the same box, and a constraint that Ball B and Ball C must be in the same box, then Balls A, B, and C must all be placed in the same box. In general, any set of balls that can be derived to be in the same box by repeatedly applying the constraints must all be placed in the same box.

Find the total number of distribution methods that satisfy all of Rules 1, 2, and 3, modulo 998244353. If no valid distribution exists, output 0.

Here, two distribution methods are considered different if there exists a ball that is placed in a box with a different number in one distribution method compared to the other.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq U_j < V_j \leq K (1 \leq j \leq M)
• All pairs (U_j, V_j) are distinct.
• All input values are integers.

Sample Input 1

2 4 1
1 2

Sample Output 1

6

Sample Input 2

3 2 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

120

Sample Input 4

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

Sample Output 4

40320

Sample Input 5

1 1 0

Sample Output 5

1

Problem Statement

Takahashi and Aoki are running on a straight running course. This course has a start point, and N water stations are aligned in a straight line ahead of it, numbered 1, 2, \ldots, N in increasing order of distance from the start point. Water station N is the goal of this course.

The distance from the start point to water station 1, as well as the distance between any two adjacent water stations, is 1. Takahashi runs at a constant speed of V per second, and Aoki runs at a constant speed of W per second.

Takahashi and Aoki may stop at each water station to hydrate. Upon arriving at water station i, Takahashi stops for R_i seconds before resuming running, and Aoki stops for S_i seconds before resuming running (if the time is 0 seconds, they pass through without stopping). However, upon arriving at the goal, water station N, they finish running immediately and do not stop for hydration, regardless of the values of R_N and S_N. A runner who has reached the goal remains at water station N until the end of the observation period.

Both runners start from the start point simultaneously at time 0 and run towards the goal (the direction in which the water station numbers increase) at their respective speeds.

Let f(t) be Takahashi's distance from the start point at time t, and g(t) be Aoki's distance from the start point at time t. We say that one runner overtakes the other when the sign of f(t) - g(t) changes. Strictly speaking, it refers to the occurrence of either of the following:

• There exists a time t_0 such that, for a sufficiently small positive number \varepsilon, f(t) < g(t) holds for t_0 - \varepsilon < t < t_0, and f(t) > g(t) holds for t_0 < t < t_0 + \varepsilon. This corresponds to Takahashi overtaking Aoki.
• There exists a time t_0 such that, for a sufficiently small positive number \varepsilon, f(t) > g(t) holds for t_0 - \varepsilon < t < t_0, and f(t) < g(t) holds for t_0 < t < t_0 + \varepsilon. This corresponds to Aoki overtaking Takahashi.

If f(t) = g(t) persists for some duration before their relative order changes, this is also counted as 1 overtaking. On the other hand, if f(t) = g(t) occurs but their relative order does not change afterwards, it is not counted as an overtaking.

Please note the following:

• At time 0, both runners are at the same position (the start point). Since there is no relative order before departure, one runner pulling ahead immediately after starting is not counted as an overtaking.
• The end of the observation period is the time T when the slower of the two runners arrives at water station N. If their relative order changes exactly at time T (i.e., t_0 = T in the definition above), it is not counted as an overtaking because the state after t_0 cannot be observed.
• If one runner passes the other who is stopped at a water station, changing their relative order, this is also counted as an overtaking according to the definition above.

Find the total number of overtakings that occur from the time they start at time 0 until time T. Count both the cases where Takahashi overtakes Aoki and where Aoki overtakes Takahashi.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq V \leq 10^9
• 1 \leq W \leq 10^9
• V \neq W
• 0 \leq R_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 2 1
0 3 0
1 0 0

Sample Output 1

1

Sample Input 2

4 1 3
2 0 4 0
0 5 0 0

Sample Output 2

2

Sample Input 3

10 5 3
0 4 1 0 6 2 0 3 5 0
2 0 5 1 0 4 3 0 2 0

Sample Output 3

5

Sample Input 4

30 7 11
0 8 0 3 12 1 0 6 4 0 10 2 5 0 7 1 0 9 3 0 11 2 6 0 4 8 0 5 1 0
4 0 9 1 0 7 2 5 0 11 3 0 6 2 0 8 1 4 0 10 2 0 7 3 0 9 1 6 0 0

Sample Output 4

8

Sample Input 5

1 1000000000 1
1000000000
0

Sample Output 5

0