Problem Statement

Takahashi is managing a flower bed. Today's task is to pour water fetched from the faucet into each flower pot.

There are N flower pots arranged in a row in the flower bed, and the i-th flower pot can hold a maximum of C_i liters of water. Currently, the i-th flower pot already contains S_i liters of water.

Takahashi fetches M liters of water from the faucet and carries it in a bucket. He visits the flower pots in the order 1, 2, \ldots, N, performing the following operation for each:

• For flower pot i, pour into flower pot i an amount of water equal to the smaller of the remaining capacity of the pot C_i - S_i liters and the amount of water currently remaining in the bucket. The water in the bucket decreases by the amount poured, and the amount of water in flower pot i increases by that same amount.

After finishing the operation for all flower pots, if there is any water remaining in the bucket, it is discarded.

Determine the amount of water in each flower pot after all operations are completed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 10^{18}
• 1 \leq C_i \leq 10^9
• 0 \leq S_i \leq C_i
• All input values are integers.

Sample Input 1

3 8
10 3
8 5
6 2

Sample Output 1

10
6
2

Sample Input 2

5 100
10 5
20 20
15 3
8 0
12 7

Sample Output 2

10
20
15
8
12

Sample Input 3

8 1000000000000
1000000000 0
500000000 200000000
1000000000 1000000000
300000000 100000000
700000000 0
400000000 400000000
600000000 150000000
200000000 50000000

Sample Output 3

1000000000
500000000
1000000000
300000000
700000000
400000000
600000000
200000000

Problem Statement

Takahashi works as a librarian at a library. The library has N bookshelves arranged in a row, numbered from 1 to N. The i-th bookshelf contains A_i books.

Aoki is going to conduct a collection survey of the library. Aoki will perform Q surveys. In the j-th survey, he specifies a range of bookshelf numbers with left endpoint L_j and right endpoint R_j, and asks Takahashi for the total number of books stored in all bookshelves from the L_j-th to the R_j-th.

For each survey, find the total number of books that Takahashi should report.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
• All input values are integers

Sample Input 1

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

Sample Output 1

8
6
14

Sample Input 2

8 5
10 20 30 40 50 60 70 80
1 1
3 6
1 8
4 7
2 5

Sample Output 2

10
180
360
220
140

Sample Input 3

10 8
1000000000 999999999 123456789 987654321 500000000 250000000 750000000 100000000 999999999 1
1 10
1 1
10 10
3 7
5 5
1 5
6 10
2 9

Sample Output 3

5711111109
1000000000
1
2611111110
500000000
3611111109
2100000000
4711111108

Problem Statement

Takahashi manages a sequence of N integers. The elements of the sequence are numbered from 1 to N from left to right, and initially all elements have a value of 0.

Takahashi performs M operations on this sequence. In the i-th operation, he adds 1 to the values of all elements whose indices are between L_i and R_i, inclusive.

After all operations have been performed, find the value of each element in the sequence.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• All inputs are integers

Sample Input 1

5 3
1 3
2 5
3 4

Sample Output 1

1 2 3 2 1

Sample Input 2

10 5
1 5
3 8
6 10
1 10
4 6

Sample Output 2

2 2 3 4 4 4 3 3 2 2

Sample Input 3

20 10
1 20
3 15
5 10
7 8
1 1
20 20
2 19
10 15
12 18
6 14

Sample Output 3

2 2 3 3 4 5 6 6 5 6 5 6 6 6 5 3 3 3 2 2

Problem Statement

Takahashi works as a driver for a delivery company. Today, he must deliver a package from point 1, where the warehouse is located, to point N, the delivery destination.

The points are numbered from 1 to N, and there are M roads connecting the points. Each road is also numbered from 1 to M. Road i (1 \leq i \leq M) bidirectionally connects point U_i and point V_i, with a normal travel time of W_i minutes. There may be multiple roads connecting the same pair of points.

However, due to road construction today, K roads are subject to speed restrictions. The numbers of the roads under speed restrictions are given as C_1, C_2, \ldots, C_K. Roads under speed restrictions are still passable, but their travel time becomes 2 times the normal time, that is, 2W_i minutes. Roads not under speed restrictions have their normal travel time of W_i minutes.

Find the shortest time (in minutes) for Takahashi to travel from point 1 to point N. If it is impossible to reach point N from point 1, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq M
• 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
• U_i \neq V_i (1 \leq i \leq M)
• 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
• 1 \leq C_j \leq M (1 \leq j \leq K)
• C_1, C_2, \ldots, C_K are all distinct
• All input values are integers

Sample Input 1

4 5 1
1 2 3
1 3 2
2 4 5
3 4 4
2 3 7
3

Sample Output 1

6

Sample Input 2

3 1 0
1 2 5

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

19

Sample Input 4

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

Sample Output 4

71

Sample Input 5

2 1 1
1 2 1000000000
1

Sample Output 5

2000000000

Sample Input 6

4 5 1
1 2 3
1 3 2
2 4 5
3 4 4
2 3 7
3

Sample Output 6

6

Sample Input 7

3 1 0
1 2 5

Sample Output 7

-1

Sample Input 8

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

Sample Output 8

19

Sample Input 9

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

Sample Output 9

71

Sample Input 10

2 1 1
1 2 1000000000
1

Sample Output 10

2000000000

Problem Statement

Takahashi places N balls numbered from 1 to N into some of M boxes numbered from 1 to M, in the order of ball 1, ball 2, \dots, ball N. Each box can hold any number of balls. Let B_i denote the box number in which ball i is placed (1 \leq B_i \leq M).

Aoki recorded the box number sequence B_1, B_2, \dots, B_N by converting it into a "compressed number sequence" C_1, C_2, \dots, C_N using the following procedure. This procedure assigns new numbers 1, 2, 3, \dots in the order of first appearance of each box number.

> Initially, no box number has a compressed number assigned to it.

>

> For i = 1, 2, \dots, N in order, do the following:

> - If box number B_i has not yet been assigned a compressed number (i.e., B_i is different from all of B_1, B_2, \dots, B_{i-1}), assign to box number B_i the smallest positive integer not yet assigned to any box number as its compressed number. Set C_i to that compressed number.

> - If box number B_i has already been assigned a compressed number (i.e., there exists some element among B_1, B_2, \dots, B_{i-1} equal to B_i), set C_i to the compressed number already assigned to box number B_i.

For example, when the box number sequence is (5, 5, 2, 7, 2), box number 5 is assigned compressed number 1, box number 2 is assigned compressed number 2, and box number 7 is assigned compressed number 3, resulting in the compressed number sequence (1, 1, 2, 3, 2).

However, part of the record became dirty and unreadable.

You are given a sequence D_1, D_2, \dots, D_N of length N. When D_i = 0, the value of C_i is unknown. When D_i \neq 0, it must hold that C_i = D_i.

Find the number of box number sequences B_1, B_2, \dots, B_N (where each B_i is an integer between 1 and M inclusive) such that the compressed number sequence C_1, C_2, \dots, C_N obtained by the above procedure satisfies all the conditions of D, modulo 998244353. Here, two box number sequences are considered distinct if there exists some i such that their values of B_i differ. If no valid box number sequence exists, output 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• N \times \min(N, M) \leq 2.5 \times 10^7
• 0 \leq D_i \leq N
• All input values are integers.

Sample Input 1

5 4
1 1 2 0 2

Sample Output 1

48

Sample Input 2

4 2
1 2 3 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

51840

Sample Input 4

24 15
1 0 2 0 3 0 1 4 0 2 5 0 0 3 6 0 4 0 6 7 0 5 0 7

Sample Output 4

280519446

Sample Input 5

1 1
0

Sample Output 5

1