Problem Statement

On the night of a summer festival, Takahashi and Aoki are watching fireworks from different locations. During the fireworks show, N fireworks are launched.

At the moment the i-th firework bursts, Takahashi is at coordinates (X_i, Y_i) and Aoki is at coordinates (P_i, Q_i) on a two-dimensional plane. Their positions may differ for each firework.

When the Euclidean distance between Takahashi and Aoki at the moment a firework bursts is at most R, we say they "watched it together." Here, the Euclidean distance between the two for the i-th firework is \sqrt{(X_i - P_i)^2 + (Y_i - Q_i)^2}.

Among the N fireworks, find the number of fireworks that the two watched together.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq R \leq 10^9
• -10^9 \leq X_i, Y_i, P_i, Q_i \leq 10^9
• All inputs are integers

Sample Input 1

3 5
0 0 3 4
0 0 6 0
1 1 1 1

Sample Output 1

2

Sample Input 2

2 1
0 0 10 10
5 5 0 0

Sample Output 2

0

Sample Input 3

6 10
0 0 3 4
0 0 8 6
0 0 11 0
5 5 5 5
-3 4 3 -4
100 100 0 0

Sample Output 3

4

Sample Input 4

10 1000000000
0 0 600000000 800000000
0 0 600000001 800000000
1000000000 1000000000 -1000000000 -1000000000
0 0 0 0
-500000000 -500000000 -500000000 -500000000
999999999 0 0 0
0 0 0 1000000000
100 200 300 400
-1000000000 0 1000000000 0
500000000 500000000 500000001 500000001

Sample Output 4

7

Sample Input 5

1 1
0 0 1 0

Sample Output 5

1

Problem Statement

Takahashi is a staff member working at a delivery center. The delivery center has N destinations, each numbered from 1 to N. He needs to deliver A_i packages to destination i.

Takahashi can visit only one destination per day and deliver at most K packages to that destination. If there are packages that cannot be delivered in a single day, he visits the same destination again on another day to deliver them. Therefore, completing the delivery to destination i takes \lceil A_i / K \rceil days, and the total number of days required to complete deliveries to all destinations is \sum_{i=1}^{N} \lceil A_i / K \rceil days.

Aoki is the manager of the delivery center and wants to reduce the number of delivery days as much as possible. To this end, Aoki is considering increasing the daily delivery capacity before deliveries begin. Specifically, Aoki can choose an integer x with 0 \leq x \leq M and change the daily delivery capacity from K to K + x. This change is made only once before deliveries start and cannot be altered during the delivery process. Note that choosing x = 0, i.e., not changing the capacity, is also allowed.

Find the minimum number of days required for Takahashi to complete all deliveries when Aoki chooses x optimally.

In other words, for an integer x satisfying 0 \le x \le M, the total number of delivery days is

\sum_{i=1}^{N} \left\lceil \frac{A_i}{K + x} \right\rceil

Output the total number of delivery days when x is chosen to minimize this value.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 0 \leq M \leq 10^9
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3 2
7 3 5

Sample Output 1

4

Sample Input 2

2 5 0
12 8

Sample Output 2

5

Sample Input 3

5 10 100
100 200 50 75 300

Sample Output 3

8

Sample Input 4

10 100 1000000000
1000000000 999999999 500000000 123456789 987654321 100000000 1 999999999 500000001 750000000

Sample Output 4

10

Sample Input 5

1 1 0
1

Sample Output 5

1

Problem Statement

Takahashi's hobby is mountain climbing, and he is compiling information about the mountains visible from observatories in various locations.

In a certain mountainous region, there are N mountains. The i-th mountain has an elevation of Y_i meters and a beauty rating of P_i.

Takahashi conducts Q surveys. In each survey, a reference elevation L_j is specified, and he wants to find the total beauty rating of all mountains whose elevation is at least L_j.

Find the answer for each survey.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq Y_i \leq 10^9
• 1 \leq P_i \leq 10^9
• 1 \leq L_j \leq 10^9
• All input values are integers

Sample Input 1

3 2
100 5
200 10
300 15
150
100

Sample Output 1

25
30

Sample Input 2

3 3
100 3
200 7
300 11
500
300
1

Sample Output 2

0
11
21

Sample Input 3

8 5
50 2
120 8
300 15
500 20
700 25
1000 30
1500 50
2000 100
600
1000
2000
2001
1

Sample Output 3

205
180
100
0
250

Sample Input 4

15 10
80 12
150 25
300 18
450 30
600 45
800 55
1200 60
1800 70
2500 85
3000 100
4000 120
5500 200
7000 150
8500 300
10000 500
1
500
1000
2000
3000
5000
7000
9000
10000
10001

Sample Output 4

1770
1685
1585
1455
1370
1150
950
500
500
0

Sample Input 5

1 1
1000000000 1000000000
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is the manager of a store with N part-time workers. He needs to complete M tasks on an upcoming holiday, and must assign exactly 1 part-time worker to each task.

The part-time workers are numbered from 1 to N, and the skill level of worker i is A_i. The tasks are numbered from 1 to M, and the required skill level of task j is D_j.

When worker i is assigned to task j, their satisfaction is calculated as A_i - D_j. Since a worker becomes dissatisfied if their satisfaction is negative, Takahashi wants to make an assignment such that every assigned worker's satisfaction is 0 or more (i.e., no one is dissatisfied).

Specifically, he selects M workers out of the N part-time workers and assigns the selected M workers to the M tasks in a one-to-one correspondence. That is, letting f(j) denote the worker assigned to task j, he considers an assignment f that satisfies all of the following conditions:

• Exactly 1 part-time worker is assigned to each task j (1 \leq j \leq M).
• Different tasks are assigned different workers. That is, if j \neq j', then f(j) \neq f(j'). (Some workers may not be assigned to any task.)
• For every worker assigned to a task, their satisfaction is 0 or more. That is, for every task j (1 \leq j \leq M), A_{f(j)} \geq D_j holds.

If an assignment satisfying these conditions exists, find the maximum value of the total satisfaction of the M assigned workers, \displaystyle\sum_{j=1}^{M}(A_{f(j)} - D_j). If no valid assignment exists, output -1.

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 D_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

4 3
5 3 7 1
2 4 6

Sample Output 1

3

Sample Input 2

3 3
1 2 3
4 5 6

Sample Output 2

-1

Sample Input 3

7 5
10 25 8 30 15 5 20
3 12 7 18 25

Sample Output 3

35

Problem Statement

Takahashi is a department manager who manages N employees. Each employee is assigned an employee number from 1 to N, and the initial evaluation points of employee i are S_i.

Let T_i denote the current evaluation points of employee i. Initially, T_i = S_i (1 \leq i \leq N).

This company has a unique evaluation system. When a certain employee k (1 \leq k \leq N) achieves results as a team leader, bonus points corresponding to the achievement are added to the evaluation points of all employees whose employee numbers are multiples of k (k, 2k, 3k, \ldots) and are at most N. Since k itself is a multiple of k, it is included in the targets.

Takahashi performs Q operations on this evaluation system. Each operation is one of the following two types:

• Operation 1: Given a positive integer k (1 \leq k \leq N) and a positive integer v. Add v to the evaluation points T_j of all employees j whose employee numbers are multiples of k and are at most N (i.e., j = k, 2k, 3k, \ldots and j \leq N).
• Operation 2: Given a positive integer x (1 \leq x \leq N). Output the sum of the current evaluation points from employee 1 to employee x: \displaystyle\sum_{i=1}^{x} T_i.

For all operations of type 2, output the correct answer.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 10^5
• 1 \leq S_i \leq 10^9
• In operation 1, 1 \leq k \leq N
• In operation 1, 1 \leq v \leq 10^9
• In operation 2, 1 \leq x \leq N
• Operation 2 is given at least once
• All input values are integers
• It is guaranteed that the values to be output are at most 2^{63} - 1 (they fit in a signed 64-bit integer)

Sample Input 1

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

Sample Output 1

6
35
2
34

Sample Input 2

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

Sample Output 2

19
6
27
10

Sample Input 3

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

Sample Output 3

23
68
65
188
3
75

Sample Input 4

20 14
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
2 20
1 4 25
1 6 10
2 12
1 1 3
2 5
1 10 100
2 20
1 7 8
1 20 50
2 19
2 20
1 3 6
2 18

Sample Output 4

2100
875
190
2515
2203
2581
2046

Sample Input 5

1 4
1000000000
2 1
1 1 1000000000
2 1
2 1

Sample Output 5

1000000000
2000000000
2000000000