Problem Statement

Takahashi is an audio engineer. He is in charge of the acoustic design of a concert venue.

There are N speakers installed on a number line in the venue, and he needs to calculate the sound intensity heard at a measurement point in the audience area. The coordinate of the measurement point is P.

The i-th speaker is installed at coordinate X_i, and its output power is V_i. The sound intensity from a speaker when it reaches the measurement point is given by its output power divided by the distance to the measurement point. That is, the sound intensity reaching the measurement point from the i-th speaker is \frac{V_i}{|X_i - P|}.

However, if a speaker is at the exact same coordinate as the measurement point (i.e., X_i = P), the distance becomes 0 and the value is undefined, so that speaker is excluded from the calculation.

Takahashi wants to calculate the total sound intensity heard at the measurement point, which is the sum of \frac{V_i}{|X_i - P|} over all i such that X_i \neq P. Find this value.

If there are no speakers to include in the calculation (i.e., all speakers are located at the measurement point), the total sum is considered to be 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq P \leq 10^9
• -10^9 \leq X_i \leq 10^9
• 1 \leq V_i \leq 10^6
• \displaystyle \sum_{i=1}^{N} V_i \leq 10^6
• N, P, X_i, and V_i are all integers.
• There may be speakers where X_i = P.

Sample Input 1

3 0
-2 4
1 3
0 5

Sample Output 1

5.00000000000000000000

Sample Input 2

4 -3
-3 10
-4 2
1 8
-1 6

Sample Output 2

7.00000000000000000000

Sample Input 3

10 7
-5 24
0 14
3 8
6 15
7 100
8 9
10 21
15 32
20 39
100 93

Sample Output 3

45.00000000000000000000

Sample Input 4

30 -1000000000
-1000000000 50000
-999999999 12000
-999999998 24000
-999999990 35000
-999999900 18000
-999999000 42000
-999990000 16000
-999900000 27000
-999000000 31000
-990000000 22000
-900000000 45000
-750000000 15000
-500000000 38000
-250000000 19000
-1 29000
0 33000
1 17000
100 26000
10000 14000
1000000 41000
100000000 23000
250000000 37000
500000000 11000
750000000 34000
900000000 21000
999000000 28000
999900000 13000
999999998 39000
999999999 20000
1000000000 43000

Sample Output 4

27723.90413112317764898762

Sample Input 5

1 1000000000
1000000000 1000000

Sample Output 5

0.00000000000000000000

Problem Statement

A certain region has N settlements, numbered from settlement 1 to settlement N. Each settlement i (1 \leq i \leq N) is located at coordinates (X_i, Y_i) on a two-dimensional plane. Note that different settlements may be located at the same coordinates.

In this region, an emergency helicopter base is to be established at one of the settlements so that each settlement can be quickly reached in case of emergency. Takahashi is the disaster prevention officer for this region and is considering the placement of the base Q times. In the k-th consideration (1 \leq k \leq Q), he considers the case where the base is established at settlement C_k. Note that the same settlement may be specified in different considerations.

For each consideration, Takahashi wants to compute the sum of Euclidean distances from the base to all settlements (including the settlement where the base is established itself). However, since the management system for this region is designed to handle only integer values, the distance to each settlement is truncated (i.e., the floor function is applied) before summing.

Specifically, when the base is established at settlement C_k, the value to be computed is

\sum_{j=1}^{N} \lfloor \sqrt{(X_{C_k} - X_j)^2 + (Y_{C_k} - Y_j)^2} \rfloor

where \lfloor x \rfloor denotes the largest integer not exceeding x.

For each consideration, compute this value.

Constraints

• 1 \leq N \leq 2000
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq X_i \leq 10^4 \quad (1 \leq i \leq N)
• 0 \leq Y_i \leq 10^4 \quad (1 \leq i \leq N)
• 1 \leq C_k \leq N \quad (1 \leq k \leq Q)
• All inputs are integers.

Sample Input 1

3 3
0 0
3 4
6 0
1
2
3

Sample Output 1

11
10
11

Sample Input 2

4 6
0 0
0 0
1 1
2 0
1
2
3
4
1
3

Sample Output 2

3
3
3
5
3
3

Sample Input 3

10 12
0 0
10 0
0 10
10 10
5 5
20 5
5 20
30 40
100 100
100 101
1
5
8
9
10
2
3
4
6
7
5
1

Sample Output 3

414
370
467
1011
1015
385
383
353
382
378
370
414

Sample Input 4

30 40
0 0
10000 0
0 10000
10000 10000
5000 5000
2500 2500
7500 2500
2500 7500
7500 7500
123 456
789 1011
2022 3033
4044 5055
6066 7077
8088 9099
9999 1
1 9999
3333 6666
6666 3333
1111 2222
2222 1111
4444 8888
8888 4444
1357 2468
2468 1357
9753 8642
8642 9753
3141 5926
2718 2818
0 0
1
2
3
4
5
30
10
15
20
25
26
27
28
29
6
7
8
9
11
12
13
14
16
17
18
19
21
22
23
24
1
30
5
15
2
3
4
27
28
10

Sample Output 4

206587
246423
236562
251008
136292
206587
196720
204145
159503
156776
225203
223246
141236
140231
143297
172264
163495
175044
177934
143957
134085
156092
246387
236525
146824
154588
161857
177860
185101
154231
206587
206587
136292
204145
246423
236562
251008
223246
141236
196720

Sample Input 5

1 5
10000 10000
1
1
1
1
1

Sample Output 5

0
0
0
0
0

Problem Statement

Takahashi manages N flower beds arranged in a row in his garden. The flower beds are numbered from 1 to N from left to right, and before any watering is done, the moisture level of flower bed i is C_i.

To water his garden efficiently each day, Takahashi uses a hose to water a contiguous range of flower beds at once. Each watering increases the moisture level of each targeted flower bed by K, and this value is the same for all waterings.

Takahashi will perform Q waterings. In the j-th watering (1 \leq j \leq Q), he targets flower beds from L_j to R_j (inclusive), increasing the moisture level of each targeted flower bed by K.

Determine the moisture level of each flower bed after all waterings are completed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq C_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
• All input values are integers

Sample Input 1

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

Sample Output 1

4 8 9 7 5

Sample Input 2

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

Sample Output 2

10 25 33 48 22 16 11

Sample Input 3

10 1000000000 5
100 200 300 400 500 600 700 800 900 1000
1 10
3 8
5 5
1 5
6 10

Sample Output 3

2000000100 2000000200 3000000300 3000000400 4000000500 3000000600 3000000700 3000000800 2000000900 2000001000

Problem Statement

Takahashi is investigating the transportation network of a country consisting of N cities. In this country, there are M one-way roads. Road i goes from city u_i to city v_i with a toll of w_i. There is at most one road for each pair of start and end cities, and there are no self-loops (roads where the start and end cities are the same).

A path from city s to city t (s \neq t) refers to a sequence of cities s = c_0, c_1, \ldots, c_l = t (l \geq 1) such that for each h = 0, 1, \ldots, l-1, there exists a road from city c_h to city c_{h+1}. Here, passing through the same city multiple times in a path is allowed. The cost of this path is the sum of the tolls of all roads passed through, that is, \displaystyle\sum_{h=0}^{l-1} w_{(c_h, c_{h+1})}, where w_{(c_h, c_{h+1})} represents the toll of the road from city c_h to city c_{h+1}.

When there is at least one path from city s to city t, a path among them with the minimum cost is called a shortest path, and its cost is called the shortest cost d(s, t). There may be multiple shortest paths.

Also, in a path c_0, c_1, \ldots, c_l, the vertices c_1, c_2, \ldots, c_{l-1} (when l \geq 2), excluding the starting vertex c_0 and the ending vertex c_l, are called the internal vertices of the path.

Takahashi wants to evaluate how important each city is as a relay point. The importance of city k (1 \leq k \leq N) is defined as follows:

The importance of city k is the number of ordered pairs of cities (i, j) (1 \leq i, j \leq N, where i, j, and k are all distinct) that satisfy the following condition:

- There is at least one shortest path from city i to city j that contains city k as an internal vertex. That is, there exists a shortest path c_0, c_1, \ldots, c_l such that c_h = k for some h (1 \leq h \leq l-1).

Since these are ordered pairs, the pairs (i, j) and (j, i) are counted separately. Also, if there is no path from city i to city j, the pair (i, j) does not contribute to the importance of any city.

If there are multiple shortest paths from city i to city j, as long as at least one of them contains city k as an internal vertex, the pair (i, j) is counted toward the importance of city k.

Find the importance of each city 1, 2, \ldots, N.

Constraints

• 2 \leq N \leq 250
• 0 \leq M \leq N(N-1)
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• 1 \leq w_i \leq 10^6
• All pairs (u_i, v_i) are distinct.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
2
2
0

Sample Input 2

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

Sample Output 2

0
1
0
0
0

Sample Input 3

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

Sample Output 3

6
6
19
0
21
15
20
19

Sample Input 4

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

Sample Output 4

63
64
4
52
42
36
24
31
25
15
17
19
35
37
9

Sample Input 5

2 0

Sample Output 5

0
0

Problem Statement

Takahashi is conducting a physics experiment on the straightness of light using a laser pointer.

There are N sensors placed on a two-dimensional plane. The i-th sensor (1 \leq i \leq N) is located at the coordinates (X_i, Y_i). Multiple sensors may be placed at the same coordinates, but they are treated as distinct sensors.

Takahashi will project a laser beam onto the plane exactly once. The laser beam is represented as a straight line on the plane (extending infinitely in both directions). Takahashi can freely choose this line from any possible line on the plane, regardless of the positions of the sensors.

Each sensor reacts if the distance from the sensor's position to the line (the shortest distance between a point and a line) is at most D. Here, D is the threshold distance for the sensors to react.

Your task is to maximize the number of reacting sensors. That is, find the maximum number of sensors i such that the distance from the point (X_i, Y_i) to a chosen line \ell is at most D, over all possible lines \ell on the plane.

Constraints

• 1 \leq N \leq 200
• 0 \leq D \leq 1000
• -1000 \leq X_i \leq 1000 (1 \leq i \leq N)
• -1000 \leq Y_i \leq 1000 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

Sample Input 2

6 0
0 0
1 1
2 2
0 2
2 0
1 0

Sample Output 2

3

Sample Input 3

20 2
-5 -6
-4 -3
-3 -3
-2 -1
-1 -2
0 1
1 0
2 2
3 4
4 3
5 6
6 5
7 7
8 10
10 8
-8 5
-6 8
3 -7
9 -4
0 0

Sample Output 3

16

Sample Input 4

60 4
-30 -62
-28 -55
-26 -51
-24 -49
-22 -43
-20 -41
-18 -34
-16 -33
-14 -27
-12 -25
-10 -18
-8 -17
-6 -11
-4 -9
-2 -2
0 -1
2 5
4 7
6 14
8 15
10 21
12 23
14 30
16 31
18 37
20 39
22 46
24 47
26 53
28 55
30 62
-50 40
-45 -10
-40 70
-35 0
-32 100
-25 80
-15 60
-5 50
5 -50
15 -60
25 -70
35 -80
45 10
50 -40
60 60
-60 -60
0 80
80 0
-80 0
0 -80
100 100
-100 100
100 -100
-100 -100
12 23
12 23
-20 -41
31 60
-31 -60

Sample Output 4

36

Sample Input 5

1 1000
-1000 1000

Sample Output 5

1