Problem Statement

Takahashi works at a woodworking workshop. The workshop has N wooden sticks, and the length of the i-th stick is A_i centimeters.

Takahashi needs to use these sticks to build a fence. To make the fence look beautiful, all sticks must be adjusted to the same positive integer length.

Takahashi can perform the following operation any number of times:

• Choose one stick and shorten its length by exactly 1 centimeter.

The same stick may be chosen multiple times. However, sticks cannot be lengthened, and the length of every stick must remain at least 1 centimeter at all times.

Takahashi is free to choose the target length. Specifically, he decides on a single positive integer T and repeats the operation until all sticks have length T centimeters. Since sticks cannot be lengthened, T must be at most the current length of every stick, i.e., 1 \leq T \leq \min(A_1, A_2, \ldots, A_N).

Find the minimum total number of operations needed to make all sticks have length T, when T is chosen optimally.

Constraints

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

Sample Input 1

3
5 3 4

Sample Output 1

3

Sample Input 2

5
10 10 10 10 10

Sample Output 2

0

Sample Input 3

7
100 45 72 89 50 63 45

Sample Output 3

149

Problem Statement

Takahashi works at the ticket window of an amusement park. Today, N customers are lined up in order, and the i-th customer has a budget of S_i yen.

The amusement park offers M types of tickets, and the j-th ticket costs G_j yen. All ticket prices are distinct. Each type of ticket can be sold at most K times in a single day.

Takahashi processes the N customers one by one in the order they are lined up (from the 1-st customer to the N-th customer), following the rules below. At most one ticket is sold to each customer, and the next customer is processed only after the current customer's processing is complete.

1. Among the tickets whose price is within the customer's budget (i.e., tickets j satisfying G_j \leq S_i), select the one with the highest price. Since all ticket prices are distinct, if there exists a ticket satisfying the condition, the selection is unique. If no ticket has a price within the customer's budget, no ticket is sold to that customer, and processing moves to the next customer.
2. For the ticket selected in step 1, if fewer than K copies have been sold today, sell one copy of that ticket. If K copies have already been sold, no ticket is sold to that customer, and processing moves to the next customer. Even if the ticket selected in step 1 cannot be sold, no other type of ticket will be sold instead.

Determine the number of customers to whom Takahashi can sell a ticket.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq S_i \leq 10^{18} (1 \leq i \leq N)
• The values of S_i may contain duplicates.
• 1 \leq G_j \leq 10^{18} (1 \leq j \leq M)
• All G_j are distinct.
• All inputs are integers.

Sample Input 1

5 3 2
10 5 8 12 6
3 7 11

Sample Output 1

5

Sample Input 2

4 2 1
5 5 3 10
5 8

Sample Output 2

2

Sample Input 3

10 5 2
100 50 30 80 60 40 90 20 70 55
25 45 65 85 100

Sample Output 3

8

Sample Input 4

20 6 3
500 200 350 700 150 600 400 250 800 100 450 550 300 650 50 750 900 200 350 600
120 280 460 590 710 850

Sample Output 4

14

Sample Input 5

1 1 1
5
10

Sample Output 5

0

Problem Statement

Takahashi is the manager of agricultural water. The region he manages has N reservoirs, numbered from 1 to N. Currently, each reservoir i (1 \leq i \leq N) stores P_i liters of water.

The region has M waterways, and the j-th waterway bidirectionally connects reservoir U_j and reservoir V_j. Note that it is not necessarily the case that all reservoirs are connected to each other through waterways.

Takahashi wants to minimize the difference between the maximum and minimum water amounts among all reservoirs. To achieve this, he can perform the following operation zero or more times, as many times as he likes. The same waterway can be used multiple times.

Operation: Choose a pair of reservoirs (u, v) that are directly connected by a waterway, and transfer exactly 1 liter of water from one to the other.

In a single operation, water can only be moved between reservoirs that are directly connected by a waterway. However, by repeating operations, water can also be transported to reservoirs that are indirectly connected through waterways. On the other hand, no matter what operations are performed, water cannot be moved between reservoirs that are not connected by any waterways.

However, for equipment maintenance purposes, immediately after every operation, the water amount in every reservoir must be at least 1 liter. That is, an operation that would result in a reservoir having 0 liters of water after sending 1 liter from it is not allowed.

Note that the water amount in each reservoir is always an integer number of liters (since the initial water amounts are integers and operations are performed in units of 1 liter).

When operations are performed optimally, find the minimum achievable value of the difference between the maximum and minimum water amounts among all reservoirs.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq P_i \leq 10^9
• 1 \leq U_j, V_j \leq N
• U_j \neq V_j (no self-loops)
• There is at most one waterway connecting the same pair of reservoirs (no multi-edges)
• All input values are integers

Sample Input 1

3 2
1 5 2
1 2
2 3

Sample Output 1

1

Sample Input 2

4 0
3 1 4 1

Sample Output 2

3

Sample Input 3

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

Sample Output 3

10

Sample Input 4

20 24
100 1 50 75 30 200 10 90 60 5 130 40 1000000000 999999999 2 3 4 500 1 1000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 6
2 7
3 8
4 9
13 14
14 15
15 16
16 17
17 18
13 16
14 17
15 18
19 20

Sample Output 4

333333353

Sample Input 5

1 0
1000000000

Sample Output 5

0

Problem Statement

Takahashi is investigating ancient ruins where stone blocks are arranged in a grid with H rows and W columns. Each cell contains a stone block, and the block at the i-th row from the top and j-th column from the left has a durability of C_{i,j}.

Wind and rain are constantly raging in the area outside the grid. Here, "outside the grid" refers to the region outside the range of rows 1 through H and columns 1 through W. Over many years, the stone blocks gradually erode starting from the surfaces that come into contact with the wind and rain.

A stone block is said to be "exposed to the wind and rain" if at least one of its four orthogonally adjacent cells (up, down, left, right) is outside the grid or is an empty cell (a cell where a stone block has collapsed and disappeared). Initially, there are no empty cells. In particular, the blocks on the boundary of the grid (1-st row, H-th row, 1-st column, and W-th column) are adjacent to the outside of the grid, so they are exposed to the wind and rain from the initial state.

Erosion progresses in units of steps, numbered starting from 1. In each step, the following Process 1 and Process 2 are performed once each in this order:

1. Durability Reduction: The durability of every stone block that is exposed to the wind and rain at the start of this step decreases by 1 simultaneously. The durability of stone blocks not exposed to the wind and rain does not change.
2. Collapse Check: All stone blocks whose durability becomes 0 as a result of Process 1 collapse simultaneously, and their cells become empty cells.

Cascading collapses do not occur within the same step. That is, even if some blocks become newly exposed to the wind and rain as a result of collapses in Process 2, the durability of those blocks will not decrease further during this step. Newly exposed blocks will begin to have their durability decreased starting from Process 1 of the next step.

Since the grid is finite and erosion progresses inward starting from the outer perimeter, all blocks will inevitably collapse within a finite number of steps. Therefore, the step number at which each cell's block collapses is uniquely determined as a finite positive integer.

Takahashi has decided to investigate the step number at which the stone block collapses for each of Q designated target cells.

The k-th target is the cell at the R_k-th row from the top and K_k-th column from the left. For each of the Q targets, find the step number at which the stone block at that cell collapses.

Constraints

• 1 \leq H \leq 500
• 1 \leq W \leq 500
• 1 \leq C_{i,j} \leq 10^9
• 1 \leq Q \leq 10^5
• 1 \leq R_k \leq H
• 1 \leq K_k \leq W
• The cells specified by the queries may contain duplicates.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
6
4
3
1

Sample Input 2

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

Sample Output 2

4
1
3
2
5
3

Sample Input 3

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

Sample Output 3

3
1
11
34
36
29
15
1
6
9
15
15

Sample Input 4

12 12
5 18 7 21 9 30 12 25 6 17 11 4
14 40 33 28 19 45 37 31 22 26 35 8
10 29 55 48 42 60 51 46 39 44 20 13
16 34 58 70 65 72 69 63 57 50 27 15
23 41 62 80 95 90 88 76 61 53 32 18
9 36 59 84 100 120 110 92 74 56 38 24
20 43 67 89 115 130 125 101 83 64 47 28
12 31 54 78 96 112 105 87 71 49 30 19
8 27 45 66 79 91 86 73 58 42 25 14
6 22 39 52 68 77 70 55 43 33 16 10
11 24 30 37 46 59 48 40 29 21 13 7
3 15 9 26 12 34 18 23 5 20 8 2
20
1 1
1 12
12 1
12 12
6 6
7 7
5 8
8 5
3 4
10 10
2 2
11 11
4 9
9 4
6 1
1 6
12 9
7 12
5 5
5 5

Sample Output 4

5
4
3
2
408
448
240
271
97
59
54
20
124
146
9
30
5
28
230
230

Sample Input 5

1 1
1000000000
5
1 1
1 1
1 1
1 1
1 1

Sample Output 5

1000000000
1000000000
1000000000
1000000000
1000000000

Problem Statement

Takahashi challenges a dungeon. The dungeon has N rooms arranged in a row, numbered room 1, room 2, \ldots, room N in order from the entrance. Each room contains exactly one monster.

When Takahashi challenges the dungeon, he proceeds one room at a time starting from room 1, then room 2, room 3, \ldots, and must fight the monster in each room. He cannot skip any rooms. To defeat the monster in room i, his combat power before the battle must be at least A_i. Upon defeating a monster, his combat power increases by B_i. If he fails to defeat a monster, Takahashi ends his exploration there. The exploration also ends if he defeats all monsters.

Q events are given in order. There are two types of events:

• 1 i a b: The information of the monster in room i is updated. From now on, the combat power required to defeat it becomes a, and the combat power gained upon defeating it becomes b.
• 2 s: Takahashi challenges the dungeon starting from room 1 with an initial combat power of s. Based on the room information at that point, determine the number of monsters Takahashi can defeat.

Each challenge of type 2 is independent of the others. A challenge does not change the room information; only type 1 events modify room information.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 10^5
• N + Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 0 \leq B_i \leq 10^9
• In type 1 events, 1 \leq i \leq N, 0 \leq a \leq 10^9, 0 \leq b \leq 10^9
• In type 2 events, 0 \leq s \leq 10^9
• There is at least one type 2 event
• All input values are integers

Sample Input 1

4 5
3 2
5 3
10 1
9 5
2 3
2 4
1 3 8 10
2 3
2 0

Sample Output 1

2
2
4
0

Sample Input 2

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

Sample Output 2

1
3
1
3

Sample Input 3

8 10
5 3
8 2
7 10
20 1
21 5
30 0
25 8
40 10
2 5
2 4
1 6 26 5
2 5
1 8 39 1
2 5
1 1 6 100
2 5
1 4 200 0
2 100

Sample Output 3

5
0
7
8
0
8

Sample Input 4

15 18
10 5
12 0
12 8
25 10
40 20
70 0
60 15
80 5
90 30
130 10
150 50
210 0
205 10
220 100
400 1
2 10
2 9
1 2 20 100
2 10
1 6 150 100
2 10
1 5 200 0
2 10
1 5 35 5
1 12 300 0
2 50
1 15 260 0
2 50
1 1 0 0
2 0
1 14 1000000000 0
2 1000000000
2 399

Sample Output 4

3
0
1
1
1
15
15
1
15
13

Sample Input 5

1 7
0 0
2 0
1 1 1000000000 1000000000
2 999999999
2 1000000000
1 1 0 1000000000
2 0
2 1

Sample Output 5

1
0
1
1
1