Problem Statement

A group of N people, including Takahashi, has come to an amusement park. This amusement park has M attractions.

Each member of the group has a certain height. The height of member j (1 \leq j \leq N) is L_j cm. Additionally, each attraction has a height restriction: to ride attraction i (1 \leq i \leq M), one must have a height of at least S_i cm. That is, member j can ride attraction i only when L_j \geq S_i is satisfied.

Takahashi wants to know how many attractions all N members of the group can ride while satisfying the height restrictions. In other words, find the number of attractions i such that L_j \geq S_i holds for every member j (1 \leq j \leq N).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq L_j \leq 300 (1 \leq j \leq N)
• 1 \leq S_i \leq 300 (1 \leq i \leq M)
• All inputs are integers.

Sample Input 1

3 4
150 140 160
130 150 145 170

Sample Output 1

1

Sample Input 2

5 6
120 135 128 140 132
110 125 130 140 135 150

Sample Output 2

1

Sample Input 3

10 8
165 172 158 180 169 175 162 170 168 155
150 160 155 170 165 180 145 175

Sample Output 3

3

Problem Statement

Takahashi is participating in an audition for a prestigious orchestra. There are N candidates participating in the audition, each numbered from 1 to N. Takahashi's number is 1.

In the audition, each candidate is given a practical skill score. The score of candidate i (1 \leq i \leq N) is S_i points.

However, just before the results are announced, M candidates submitted withdrawal notices. The numbers of the candidates who withdrew are D_1, D_2, \ldots, D_M. Takahashi does not withdraw (that is, it is guaranteed that D_j \neq 1).

The remaining candidates, after excluding those who withdrew, are ranked in descending order of score. If multiple candidates have the same score, the candidate with the smaller number is ranked higher. Under this rule, a unique rank is determined for all remaining candidates. The top K candidates in this ranking pass the audition.

It is guaranteed that the number of candidates after excluding those who withdrew is at least K.

Determine whether Takahashi can pass the audition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 0 \leq M \leq N - 1
• K \leq N - M
• 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq D_j \leq N (1 \leq j \leq M)
• D_j \neq 1 (1 \leq j \leq M)
• D_1, D_2, \ldots, D_M are all distinct
• All input values are integers

Sample Input 1

5 2 1
80 100 90 70 60
2

Sample Output 1

Yes

Sample Input 2

7 3 0
85 90 85 85 70 60 50

Sample Output 2

Yes

Sample Input 3

10 2 3
30 95 88 76 100 60 92 55 40 85
4 6 8

Sample Output 3

No

Problem Statement

Takahashi runs a factory and earns profit by manufacturing and selling N types of products.

The factory has M manufacturing machines. Each machine has an available operating time of K minutes, and the total manufacturing time of products produced on each machine must not exceed K minutes.

For each product i (1 \leq i \leq N), the following information is given:

• C_i: The raw material cost to manufacture one unit of product i (yen)
• T_i: The time required to manufacture one unit of product i (minutes)
• P_i: The selling price of one unit of product i (yen)

Manufacturing and selling one unit of product i yields a profit of P_i - C_i yen (if this value is negative, it represents a loss).

Each machine can only manufacture one product at a time, and manufacturing of a product cannot be interrupted midway. Once the manufacturing of one product is completed, the next product can be started immediately without any switching time.

The M machines operate independently of each other. There are sufficient raw materials, and any type of product can be manufactured without an upper limit on quantity. The types and quantities of products manufactured on each machine can be freely chosen for each machine, and the same type of product can be manufactured on multiple machines.

It is also permitted for a machine to manufacture no products at all. The profit from a machine that manufactures no products is 0 yen.

Find the maximum total profit that can be obtained from all M machines.

Constraints

• 1 \leq N \leq 500
• 1 \leq M \leq 10^9
• 1 \leq K \leq 200{,}000
• 1 \leq C_i \leq 10^6 (1 \leq i \leq N)
• 1 \leq T_i \leq K (1 \leq i \leq N)
• 1 \leq P_i \leq 10^6 (1 \leq i \leq N)
• All inputs are integers.
• It is guaranteed that the answer does not exceed 2^{63} - 1 (= 9{,}223{,}372{,}036{,}854{,}775{,}807, the maximum value of a 64-bit signed integer).

Sample Input 1

3 2 10
3 4 10
2 3 8
5 6 12

Sample Output 1

38

Sample Input 2

2 3 5
10 2 8
7 5 6

Sample Output 2

0

Sample Input 3

8 100 1000
120 50 260
200 80 390
90 30 150
300 120 500
500 200 850
40 25 70
1000 500 1600
250 70 410

Sample Output 3

280000

Sample Input 4

25 123456789 200000
100000 1 100500
200000 7 203000
300000 13 306500
400000 29 414000
500000 100 560000
600000 256 720000
700000 999 1000000
150000 1234 260000
250000 4096 450000
350000 8192 690000
450000 15000 900000
550000 20000 950000
650000 30000 980000
750000 50000 990000
800000 75000 1000000
900000 100000 1000000
100000 11111 180000
200000 22222 350000
300000 33333 520000
400000 44444 710000
500000 55555 830000
600000 66666 920000
700000 77777 970000
800000 88888 990000
900000 199999 1000000

Sample Output 4

14814814680000000

Sample Input 5

1 1 1
1 1 1

Sample Output 5

0

Problem Statement

Takahashi is in charge of directing a fireworks show. In the night sky, N fireworks are prepared for launch, numbered from 1 to N.

Each firework has one of three states: ready, launched, or destroyed. Initially, all fireworks are in the ready state.

For each firework i (1 \leq i \leq N), a "shockwave target" firework number T_i is assigned (T_i \neq i).

Aoki, as the director, decides the order in which to launch the fireworks one by one. Specifically, the fireworks show proceeds as follows:

1. Aoki selects one firework from among the ready fireworks and launches it. The launched firework's state becomes launched, and it is recorded at the end of the performance list.
2. Let i be the launched firework. If firework T_i, the shockwave target of firework i, is still in the ready state, then firework T_i detonates prematurely and its state changes to destroyed (it is not recorded in the performance list). If firework T_i is already launched or destroyed, nothing happens.
3. If one or more ready fireworks remain, return to step 1. If no ready fireworks remain, the fireworks show ends.

Note: Destroyed fireworks cannot be launched. Additionally, destroyed fireworks do not emit shockwaves, and destruction does not cause chain detonations of other fireworks.

When the fireworks show ends, the performance list is finalized. Aoki wants to maximize the number of fireworks recorded in the performance list (that is, the number of fireworks that were launched).

Determine the maximum number of fireworks recorded in the performance list when Aoki chooses optimally.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq T_i \leq N (1 \leq i \leq N)
• T_i \neq i (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

4
2 1 4 3

Sample Output 1

2

Sample Input 2

4
2 3 4 1

Sample Output 2

3

Sample Input 3

10
2 3 1 5 6 4 1 3 6 7

Sample Output 3

8

Sample Input 4

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

Sample Output 4

16

Sample Input 5

2
2 1

Sample Output 5

1

Problem Statement

N players are standing in a row, numbered 1, 2, \ldots, N from left to right.

Each player i (1 \leq i \leq N) has the following information:

• Catching Power D_i: They can catch a ball with a speed less than or equal to this value.
• Passing Range [L_i, R_i]: An interval satisfying L_i \leq i \leq R_i that represents the range of players to whom they can pass the ball. This interval always contains player i's own position.

Takahashi will throw M balls to these players. Each ball j (1 \leq j \leq M) has an initial speed W_j and is initially handed to player T_j. The M balls are processed independently, and the result of one ball does not affect any other balls.

A player who receives a ball (including the player who receives it initially) acts according to the following rules:

Suppose player i receives a ball with speed W (note that W may become 0 through repeated passes).

1. If W \leq D_i (Catch): Player i catches the ball. The movement of the ball ends here.
2. If W > D_i (Pass): Player i cannot catch the ball and attempts to pass it.

• If L_i = R_i = i (i.e., there is no player other than themselves in their passing range): They cannot make a pass, and player i becomes the final holder of the ball. The movement of the ball ends here.
• Otherwise: They pass the ball to the player with the smallest index other than player i themselves among the players in player i's passing range [L_i, R_i]. At this time, the speed of the ball decreases by 1 to become W - 1. The receiver of the pass can be either to the left (smaller index) or to the right (larger index) of player i.

Since passes can also be made to the left, the same player may be visited multiple times. However, since the speed decreases by 1 with each pass and D_i \geq 0 holds for all players, the movement of each ball is guaranteed to end after a finite number of steps.

For each of the M balls, output the final result. If the ball is caught (ends by rule 1 above), output -1. If there is a final holder (ends by the former case of rule 2 above), output the index of that player.

Constraints

• 1 \leq N, M \leq 2 \times 10^5
• N + M \leq 2 \times 10^5
• 0 \leq D_i \leq 10^9
• 1 \leq L_i \leq i \leq R_i \leq N
• 1 \leq T_j \leq N
• 1 \leq W_j \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

-1
-1
-1
4
4

Sample Input 2

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

Sample Output 2

-1
-1
-1
-1

Sample Input 3

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

Sample Output 3

1
1
-1
-1
-1
-1
1
-1
-1
-1

Sample Input 4

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

Sample Output 4

-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
15

Sample Input 5

1 2
0 1 1
1 1
1 1000000000

Sample Output 5

1
1