Problem Statement

Takahashi plans to take an N-day vacation. The forecasted temperature on day i (1 \leq i \leq N) is T_i ℃.

Takahashi considers a day to be a "nice day for an outing" if the temperature is at least L ℃ and at most R ℃.

Out of the N days, determine how many are nice days for an outing.

Constraints

• 1 \leq N \leq 10^5
• -100 \leq L \leq R \leq 100
• -100 \leq T_i \leq 100
• All inputs are integers

Sample Input 1

5 20 25
18
20
22
25
30

Sample Output 1

3

Sample Input 2

4 10 12
9
13
0
100

Sample Output 2

0

Sample Input 3

10 -5 5
-10
-5
-3
0
4
5
6
10
-1
-6

Sample Output 3

6

Sample Input 4

20 15 30
12
15
18
21
24
27
30
33
14
16
19
22
25
28
31
29
17
13
30
20

Sample Output 4

15

Sample Input 5

1 -100 -100
-100

Sample Output 5

1

Problem Statement

Takahashi manages a vast farm. The farm has N fields arranged in a row from east to west, and each field is numbered from 1 to N in order from west to east. The harvest yield of field i (1 \leq i \leq N) is A_i.

To improve the efficiency of farm management, Takahashi has decided to divide these fields into M sections. Each section consists of consecutively numbered fields. Specifically, the j-th section (1 \leq j \leq M) consists of consecutive fields from field L_j to field R_j (L_j \leq R_j). Every field belongs to exactly one section, and no field is shared between sections. Note that the sections are not necessarily given in order from west to east in the input.

The productivity of each section is defined as the sum of the harvest yields of all fields contained in that section. That is, the productivity of the j-th section is A_{L_j} + A_{L_j+1} + \cdots + A_{R_j}.

Takahashi wants to understand the variation in productivity among the sections. This is because if the difference in productivity is too large, it becomes difficult to allocate workers and distribute resources.

For the given partitioning, find the value obtained by subtracting the minimum productivity from the maximum productivity among the M sections.

Constraints

• 1 \leq M \leq N \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 M)
• The M sections partition fields 1 through N completely without overlap or omission
• The sections are not necessarily given in order from west to east in the input
• All input values are integers

Sample Input 1

5 3
10 20 30 40 50
1 2
3 3
4 5

Sample Output 1

60

Sample Input 2

8 4
5 15 10 20 25 5 30 10
1 3
4 4
5 6
7 8

Sample Output 2

20

Sample Input 3

12 5
100 200 300 150 250 50 400 100 200 300 150 100
1 2
3 5
6 8
9 10
11 12

Sample Output 3

450

Problem Statement

Takahashi is the coach of a sports club with N players. Initially, each player belongs to a separate team consisting of only themselves. Each team can have one flag color, but in the initial state, no team has a flag color assigned.

Takahashi performs M operations in order.

In the i-th operation, the following is done:

1. The team to which player U_i belongs and the team to which player V_i belongs are merged into a single team. However, if the two players already belong to the same team, no merge is performed and that team is used as the target.
2. The flag color of the resulting team is set to C_i. Any previous flag color is overwritten.

After all operations are completed, consider the teams that have a flag color assigned. Determine the number of distinct colors that appear as flag colors among those teams. Teams that were never the target of any operation (teams with no flag color assigned) are ignored.

Constraints

• 1 \leq N \leq 200000
• 1 \leq M \leq 150000
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• 1 \leq C_i \leq 10^9
• All input values are integers.

Sample Input 1

4 3
1 2 10
3 4 20
2 3 10

Sample Output 1

1

Sample Input 2

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

Sample Output 2

2

Sample Input 3

10 9
1 2 10
2 3 20
4 5 10
6 7 30
8 9 30
1 3 40
5 6 20
7 4 50
9 10 50

Sample Output 3

2

Sample Input 4

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

Sample Output 4

3

Sample Input 5

2 1
1 2 1000000000

Sample Output 5

1

Problem Statement

Takahashi lives in a city consisting of N intersections and M bidirectional roads. The intersections are numbered from 1 to N, and the i-th road connects intersection u_i and intersection v_i. There are no self-loops (roads connecting an intersection to itself), and there is at most one road connecting any pair of intersections.

For each intersection, the number of roads connected to that intersection is called the congestion level of that intersection.

Takahashi wants to travel from intersection 1 to intersection N, but he dislikes congested intersections.

Takahashi's route is represented as a sequence of intersections p_0, p_1, p_2, \ldots, p_L (L \geq 1), where p_0 = 1, p_L = N, and for each j = 0, 1, \ldots, L-1, there must exist a road connecting intersection p_j and intersection p_{j+1}. It is allowed to pass through the same intersection or the same road multiple times.

The time (in minutes) required for this route is the sum of the following two components:

1. Road travel time: The number of times roads are traversed along the route, namely L minutes. Each road traversal takes exactly 1 minute, and if the same road is traversed multiple times, each traversal is counted.
2. Intersection passing time: For each of p_1, p_2, \ldots, p_{L-1} (excluding the first element p_0 and the last element p_L of the route), if the congestion level of that intersection is K or more, an additional 1 minute is incurred. This is due to waiting at traffic lights or navigating through crowds. If the same intersection appears multiple times among p_1, p_2, \ldots, p_{L-1}, the check is performed for each occurrence, and the additional time is added for each qualifying occurrence.

Only the occurrences as the first element p_0 and the last element p_L of the route are exempt from the passing time check. For example, even intersections 1 or N, if they appear as any of p_1, p_2, \ldots, p_{L-1}, are subject to the passing time check.

Find the minimum time required for Takahashi to travel from intersection 1 to intersection N. If no route from intersection 1 to intersection N exists, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• There is at most one road connecting any pair of intersections
• All input values are integers

Sample Input 1

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

Sample Output 1

3

Sample Input 2

4 2 2
1 2
3 4

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

5

Problem Statement

Takahashi is planning a photo tour by selecting a single K \times K square area from a sightseeing region represented as an N \times N grid. The cell in the i-th row from the top and the j-th column from the left has a scenery score of A_{i,j}.

Here, a K \times K area refers to the set of all K \times K cells from row r to row r+K-1 and from column c to column c+K-1, where integers r, c are chosen such that 1 \leq r \leq N-K+1 and 1 \leq c \leq N-K+1.

Aoki, who runs a rival tour company, learns which area Takahashi has chosen, and then selects exactly one cell within that area to change its scenery score to 0 (the scenery scores of all other cells remain unchanged). Aoki must perform this operation, and may choose a cell whose score is already 0. Aoki selects the cell so as to minimize the total scenery score within the area after the operation.

The total scenery score of the K \times K cells in the area after Aoki's operation is called the satisfaction. Takahashi, taking Aoki's sabotage into account, chooses the area to maximize the satisfaction. Find the maximum value of the satisfaction.

Constraints

• 1 \leq K \leq N \leq 1000
• 0 \leq A_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

3 2
1 2 3
4 5 6
7 8 9

Sample Output 1

19

Sample Input 2

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

Sample Output 2

43

Sample Input 3

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

Sample Output 3

37

Sample Input 4

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

Sample Output 4

132

Sample Input 5

1 1
1000000000

Sample Output 5

0