Problem Statement

There are N students in Takahashi's class. Each student is assigned an attendance number from 0 to N - 1. Initially, only the student with attendance number 0 knows a certain rumor.

The rumor spreads when a student who knows it directly tells it to another student. You are given M records of rumor transmission attempts. The i-th record (a_i, b_i) means "the student with attendance number a_i attempted to tell the rumor to the student with attendance number b_i."

The records are processed in order i = 1, 2, \ldots, M. When processing the i-th record, if the student with attendance number a_i knows the rumor at that point, then the student with attendance number b_i also comes to know the rumor (if they already know it, nothing changes). If the student with attendance number a_i does not know the rumor at that point, nothing happens for this record.

A student who newly learns the rumor from a certain record can become a transmitter of the rumor in subsequent records.

After processing all records, find the total number of students who know the rumor.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 10^5
• 0 \leq a_i \leq N - 1
• 0 \leq b_i \leq N - 1
• a_i \neq b_i
• The same pair (a_i, b_i) may appear multiple times
• All input values are integers

Sample Input 1

4 3
0 1
1 2
3 2

Sample Output 1

3

Sample Input 2

4 3
1 2
0 1
2 3

Sample Output 2

2

Sample Input 3

8 13
0 3
2 4
3 2
4 5
5 1
1 7
6 7
7 6
0 2
2 4
4 5
5 6
6 7

Sample Output 3

7

Sample Input 4

15 28
0 4
1 2
4 1
2 3
3 5
6 7
5 6
8 9
7 8
10 11
11 12
12 13
13 14
0 10
9 10
14 2
4 6
6 1
1 9
9 11
11 13
13 12
12 14
14 5
5 6
6 7
7 8
8 9

Sample Output 4

13

Sample Input 5

1 0

Sample Output 5

1

Problem Statement

Takahashi is a DJ at a music festival. He plans to play N songs in his next stage, but he needs to carefully arrange the playing order so that the audience can enjoy it without feeling any discomfort.

Each song i (1 \leq i \leq N) has an integer "tempo value" A_i. The tempo value quantifies the mood of the song, and songs with close tempo values have a similar impression. Additionally, a non-negative integer D is given. Two songs whose absolute difference in tempo values is at most D are considered "similar."

Takahashi will play all N songs exactly once in any order he chooses. Let B_j be the tempo value of the j-th song played in this order. That is, (B_1, B_2, \ldots, B_N) is a permutation of (A_1, A_2, \ldots, A_N) (as multisets).

The "discomfort score" of the j-th song in the playing order is defined as follows:

• If j = 1 (the first song), the discomfort score is 0.
• If j \geq 2 (the second song or later), it is determined by whether there exists a song similar to the j-th song among the previously played songs B_1, B_2, \ldots, B_{j-1} (i.e., whether there exists k (1 \leq k \leq j-1) such that |B_j - B_k| \leq D):
• If it exists: Since a song with a similar tempo was played in the past, the audience does not feel discomfort. The discomfort score is 0.
• If it does not exist: Since the absolute difference in tempo values between this song and any of the previously played songs is strictly greater than D, the sudden change in tempo from the immediately preceding song causes discomfort. The discomfort score is |B_j - B_{j-1}|.

The sum of the discomfort scores of all songs is called the "total discomfort." Find the minimum possible total discomfort when Takahashi chooses the playing order optimally.

Constraints

• 1 \leq N \leq 10^6
• 0 \leq D \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5 3
10 13 20 22 40

Sample Output 1

25

Sample Input 2

6 0
5 5 10 10 15 30

Sample Output 2

25

Sample Input 3

15 4
32 10 14 18 50 54 55 80 83 120 121 124 200 205 209

Sample Output 3

175

Sample Input 4

30 10
100 5 15 25 40 42 60 70 71 85 95 130 131 140 150 300 305 315 500 510 520 700 701 710 900 920 940 960 980 1000

Sample Output 4

882

Sample Input 5

1 1000000000
1000000000

Sample Output 5

0

Problem Statement

A school has N students, numbered from 1 to N.

Rumors spread in a unique way at this school. There are M directed transmission relationships between students, and the i-th transmission relationship is represented by the ordered pair (u_i, v_i). This means a one-way relationship: "if student u_i receives a rumor at a certain step, the rumor is transmitted to student v_i at the next step."

The propagation of the rumor proceeds synchronously through steps 0, 1, 2, \ldots. Let A_t denote the set of students who receive the rumor at each step t. A_t is determined as follows:

• Step 0: Initially, student S hears the rumor from an external source. A_0 = \{S\}.
• Step t \geq 1: Only the students who received the rumor at the immediately preceding step t-1 (i.e., the elements of A_{t-1}) transmit the rumor. Specifically, for all transmission relationships (u, v) satisfying u \in A_{t-1}, student v receives the rumor at step t. That is,

A_t = \{v \mid \text{there exists } u \in A_{t-1} \text{ such that there is a transmission relationship } (u, v)\}

Here are some important supplementary notes:

• A student can only transmit the rumor during the single step immediately after they themselves received it. A student not in A_{t-1} does not transmit the rumor to anyone at step t, even if they received the rumor at some past step.
• Since A_t is a set, even if a student receives the rumor from multiple students simultaneously at step t, they are counted only once in A_t.
• Even if a student has already heard the rumor at a past step, they may be included in A_t again at a different step. In particular, when the graph contains cycles, the same student may receive the rumor at multiple different steps.
• If no student is reachable via transmission relationships from any element of A_{t-1}, then A_t = \emptyset (the empty set), and A_t = \emptyset for all subsequent steps as well.

For each student i, let T_i = \{t \geq 0 \mid i \in A_t\} be the set of steps at which student i receives the rumor. For example, if student i receives the rumor at steps 0, 2, 5, then T_i = \{0, 2, 5\}. (Due to the existence of cycles, T_i may be an infinite set, but since the queries below only ask about the range K_j \leq N, it suffices to consider only a finite range.)

The student S who first hears the rumor can be freely chosen from any of the students 1 to N.

Q queries are given. For the j-th query, a non-negative integer K_j (0 \leq K_j \leq N) is given. Determine the following value:

Among all choices of the student S who first hears the rumor, the number of choices of S such that all students (from 1 to N) receive the rumor at least once during the period from step 0 to step K_j (inclusive of both endpoints).

In other words, find the number of S (1 \leq S \leq N) such that for all students i (1 \leq i \leq N), T_i \cap \{0, 1, \ldots, K_j\} \neq \emptyset holds.

Constraints

• 1 \leq N \leq 2000
• 0 \leq M \leq \min(N(N-1), 50000)
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i (no self-loops)
• There are no duplicate transmission relationships. That is, if i \neq j then (u_i, v_i) \neq (u_j, v_j)
• 0 \leq K_j \leq N
• All input values are integers

Sample Input 1

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

Sample Output 1

0
0
0
4
4

Sample Input 2

3 2 4
1 2
2 1
0
1
2
3

Sample Output 2

0
0
0
0

Sample Input 3

8 14 8
1 2
1 3
2 4
3 4
4 5
5 6
6 4
5 7
7 8
8 5
2 6
3 7
6 8
8 1
0
1
2
3
4
5
6
8

Sample Output 3

0
0
0
3
7
8
8
8

Sample Input 4

16 40 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 1
1 5
1 9
2 6
2 10
3 7
3 11
4 8
4 12
5 9
5 13
6 10
6 14
7 11
7 15
8 12
8 16
9 13
9 1
10 14
10 2
11 15
11 3
12 16
12 4
0
1
2
3
4
5
6
8
10
12
15
16

Sample Output 4

0
0
0
0
0
13
14
16
16
16
16
16

Sample Input 5

1 0 4
0
1
0
1

Sample Output 5

1
1
1
1

Problem Statement

There is a board with numbers arranged in a triangular shape. The i-th row from the top contains i cells arranged in a horizontal line, and the number written in the p-th cell from the left in the i-th row (1 \leq p \leq i) is denoted A_{i,p}. The board has N rows in total.

For a non-negative integer x, define S(x) as the sum of the digits in the decimal representation of x. For example, S(0) = 0, S(19) = 10, S(999) = 27.

Furthermore, for a non-negative integer V, define f(V) = \max_{0 \leq Y \leq V} S(Y). That is, f(V) is the maximum digit sum among all integers from 0 to V inclusive.

Takahashi places a piece on a cell and repeatedly performs one of the following 3 operations:

• Stay: Stay on the current cell. (Can always be chosen regardless of the current row.)
• Move directly below: When currently on the p-th cell from the left in row i, move to the p-th cell from the left in row i+1. (Can only be chosen when i < N.)
• Move diagonally right-down: When currently on the p-th cell from the left in row i, move to the (p+1)-th cell from the left in row i+1. (Can only be chosen when i < N.)

Q queries are given. The j-th query provides a starting row L_j, a starting position P_j, and a number of operations T_j.

If P_j > L_j, then the P_j-th cell from the left does not exist in row L_j, so output NA for this query.

If P_j \leq L_j, place the piece on the P_j-th cell from the left in row L_j and perform exactly T_j operations. Considering all possible choices of sequences of T_j operations, the set of all cells where the piece can ultimately be located is called the set of reachable cells. (For example, choosing "Stay" T_j times reaches the starting cell, so the starting cell is always reachable.)

For all cells in the set of reachable cells, compute f(A_{i,p}) for the value A_{i,p} written on that cell, and output the maximum among these values.

Constraints

• 1 \leq N \leq 1000
• 1 \leq Q \leq 10^5
• NQ \leq 10^7
• 0 \leq A_{i,p} \leq 10^{18}
• 1 \leq L_j \leq N
• 1 \leq P_j \leq N (if P_j > L_j, the starting cell does not exist)
• 0 \leq T_j \leq 10^9
• All inputs are integers

Sample Input 1

4 5
5
12 30
7 99 100
0 19 88 123
1 1 0
1 1 1
2 1 2
3 2 10
4 4 1

Sample Output 1

5
11
18
18
18

Sample Input 2

3 5
8
10 29
1000 909 555
1 2 0
2 3 5
1 1 2
3 1 0
2 2 1

Sample Output 2

NA
NA
27
27
26

Sample Input 3

7 10
0
9 10
18 99 100
123 4567 890 9999
1000000000000000000 999999999999999999 123456789012345678 400000000000000000 101010101010101010
1 20 300 4000 50000 600000
987654321 123456789 111111111 222222222 333333333 444444444 555555555
1 1 6
2 2 3
3 1 0
3 4 1
5 3 2
6 6 1000000000
7 1 5
4 2 1
2 1 4
7 7 0

Sample Output 3

162
162
9
NA
153
76
80
162
162
76

Sample Input 4

12 20
42
7 88
1234 99999 100000
314159 271828 161803 141421
999999999999999999 1000000000000000000 987654321098765432 123456789012345678 555555555555555555
0 1 8 17 26 35
44 53 62 71 80 89 98
107 116 125 134 143 152 161 170
179 188 197 206 215 224 233 242 251
260 269 278 287 296 305 314 323 332 341
350 359 368 377 386 395 404 413 422 431 440
449 458 467 476 485 494 503 512 521 530 539 548
1 1 11
1 2 5
2 1 0
2 2 100
3 3 2
4 1 8
5 2 7
5 6 1
6 4 3
7 7 0
8 3 1000000000
9 9 4
10 5 2
11 1 1
12 12 0
12 1 100
4 4 10
6 1 5
3 1 9
10 11 0

Sample Output 4

162
NA
7
162
161
162
162
NA
19
17
22
22
22
21
22
21
157
20
162
NA

Sample Input 5

1 4
1000000000000000000
1 1 0
1 1 1
1 1 1000000000
1 1 999999999

Sample Output 5

162
162
162
162

Problem Statement

Takahashi manages a signal converter consisting of N steps. This converter receives an integer signal with a value between 1 and K inclusive, applies conversion processing, and produces an output.

The input signal undergoes conversion processing in order: step 1, step 2, \ldots, step N. Step i (1 \leq i \leq N) is defined by a tuple of integers (L_i, R_i, X_i) and performs the following operation:

• Let v be the signal value at the start of this step's processing. If L_i \leq v \leq R_i, replace the signal value with X_i. Otherwise, the signal value remains unchanged.

The signal value after each step's processing becomes the input to the next step, and the signal value after step N's processing becomes the final output of the converter. When the input signal value is an integer s, we define the final output signal value as F(s).

Aoki sends Q queries. In the j-th query, integers A_j and B_j are given. When the input signal values are all integers from A_j to B_j inclusive, find the number of distinct values that appear as output signal values, that is, the number of elements in the set \{F(s) \mid s \text{ is an integer}, A_j \leq s \leq B_j\}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• N \times K \leq 10^7
• N + Q \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq K (1 \leq i \leq N)
• 1 \leq X_i \leq K (1 \leq i \leq N)
• 1 \leq A_j \leq B_j \leq K (1 \leq j \leq Q)
• All inputs are integers.

Sample Input 1

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

Sample Output 1

1
1
1
1

Sample Input 2

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

Sample Output 2

1
1
1
1
1

Sample Input 3

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

Sample Output 3

1
1
1
1
1
1
1
1

Sample Input 4

20 50 12
1 10 25
11 20 5
21 30 40
31 40 15
41 50 1
5 25 33
26 45 12
1 3 50
48 50 7
7 18 22
19 32 44
33 44 9
9 9 30
30 35 2
2 8 16
16 16 41
41 49 6
6 14 28
28 38 11
11 27 35
1 50
1 10
11 20
21 30
31 40
41 50
5 45
13 37
25 25
2 49
17 33
39 50

Sample Output 4

1
1
1
1
1
1
1
1
1
1
1
1

Sample Input 5

1 1 1
1 1 1
1 1

Sample Output 5

1