D - Total Sales Within Delivery Range Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

ある街には N 軒の店舗がある。街は整数座標の平面で表され、i 番目の店舗は座標 (X_i, Y_i) にあり、その売上は C_i 円である。なお、同じ座標に複数の店舗が存在することもある。

青木君は M 個の配達拠点の候補を考えている。j 番目の候補では、座標 (P_j, Q_j) に拠点を置き、マンハッタン距離で K_j 以下の範囲を配達圏内とする。

すなわち、j 番目の候補の拠点から店舗 i が 配達可能 であるとは、

| X_i - P_j | + | Y_i - Q_j | \le K_j

を満たすことをいう。

各候補について、配達可能な店舗の売上の合計を求めてください。ただし、配達可能な店舗が存在しない場合は 0 を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • N + M \leq 1.5 \times 10^5
  • 0 \leq X_i \leq 1000
  • 0 \leq Y_i \leq 1000
  • 1 \leq C_i \leq 10^4
  • 0 \leq P_j \leq 1000
  • 0 \leq Q_j \leq 1000
  • 0 \leq K_j \leq 2000
  • 入力はすべて整数である

入力

N M
X_1 Y_1 C_1
X_2 Y_2 C_2
\vdots
X_N Y_N C_N
P_1 Q_1 K_1
P_2 Q_2 K_2
\vdots
P_M Q_M K_M
  • 1 行目には、店舗の数 N と、配達拠点の候補数 M が、スペース区切りで与えられる。
  • 続く N 行では、各店舗の情報が与えられる。
  • 1 + i 行目には、i 番目の店舗の座標 (X_i, Y_i) と、その売上 C_i が、スペース区切りで与えられる。
  • 続く M 行では、各候補の情報が与えられる。
  • 1 + N + j 行目には、j 番目の候補の拠点座標 (P_j, Q_j) と配達距離の上限 K_j が、スペース区切りで与えられる。

出力

j 行目 (1 \leq j \leq M) に、j 番目の候補で配達可能な店舗の売上の合計を出力せよ。

入力例 1

4 3
0 0 10
1 0 20
2 2 30
1 1 40
0 0 0
1 0 1
2 1 2

出力例 1

10
70
90

入力例 2

5 4
2 3 15
2 3 25
5 5 40
0 1 10
3 1 30
2 3 0
4 4 1
3 2 2
0 0 10

出力例 2

40
0
70
120

入力例 3

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

出力例 3

11
45
69
127
0
60
0

入力例 4

22 10
0 0 5
100 200 7
150 150 9
200 100 11
250 300 13
300 250 15
400 400 17
500 500 19
600 450 21
700 700 23
800 200 25
900 900 27
1000 1000 29
1000 0 31
0 1000 33
450 550 35
550 450 37
350 650 39
650 350 41
200 800 43
800 800 45
500 0 47
0 0 0
1000 1000 0
500 500 100
500 500 1000
250 250 150
750 250 100
0 1000 200
1000 0 500
300 700 200
400 100 250

出力例 4

5
29
91
572
28
25
33
103
82
73

入力例 5

1 4
1000 1000 9999
1000 1000 0
999 1000 0
0 0 1999
0 0 2000

出力例 5

9999
0
0
9999

Score : 400 pts

Problem Statement

A town has N shops. The town is represented as a plane with integer coordinates, where the i-th shop is located at coordinates (X_i, Y_i) and has sales of C_i yen. Note that multiple shops may exist at the same coordinates.

Aoki is considering M candidate locations for a delivery hub. For the j-th candidate, a hub is placed at coordinates (P_j, Q_j), and the delivery range covers all locations within Manhattan distance K_j.

Specifically, shop i is deliverable from the hub of the j-th candidate if and only if:

| X_i - P_j | + | Y_i - Q_j | \le K_j

For each candidate, find the total sales of all deliverable shops. If no shops are deliverable, output 0.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • N + M \leq 1.5 \times 10^5
  • 0 \leq X_i \leq 1000
  • 0 \leq Y_i \leq 1000
  • 1 \leq C_i \leq 10^4
  • 0 \leq P_j \leq 1000
  • 0 \leq Q_j \leq 1000
  • 0 \leq K_j \leq 2000
  • All input values are integers

Input

N M
X_1 Y_1 C_1
X_2 Y_2 C_2
\vdots
X_N Y_N C_N
P_1 Q_1 K_1
P_2 Q_2 K_2
\vdots
P_M Q_M K_M
  • The first line contains the number of shops N and the number of hub candidates M, separated by a space.
  • The following N lines give the information for each shop.
  • The (1 + i)-th line contains the coordinates (X_i, Y_i) of the i-th shop and its sales C_i, separated by spaces.
  • The following M lines give the information for each candidate.
  • The (1 + N + j)-th line contains the hub coordinates (P_j, Q_j) and the maximum delivery distance K_j for the j-th candidate, separated by spaces.

Output

On the j-th line (1 \leq j \leq M), output the total sales of the shops deliverable under the j-th candidate.

Sample Input 1

4 3
0 0 10
1 0 20
2 2 30
1 1 40
0 0 0
1 0 1
2 1 2

Sample Output 1

10
70
90

Sample Input 2

5 4
2 3 15
2 3 25
5 5 40
0 1 10
3 1 30
2 3 0
4 4 1
3 2 2
0 0 10

Sample Output 2

40
0
70
120

Sample Input 3

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

Sample Output 3

11
45
69
127
0
60
0

Sample Input 4

22 10
0 0 5
100 200 7
150 150 9
200 100 11
250 300 13
300 250 15
400 400 17
500 500 19
600 450 21
700 700 23
800 200 25
900 900 27
1000 1000 29
1000 0 31
0 1000 33
450 550 35
550 450 37
350 650 39
650 350 41
200 800 43
800 800 45
500 0 47
0 0 0
1000 1000 0
500 500 100
500 500 1000
250 250 150
750 250 100
0 1000 200
1000 0 500
300 700 200
400 100 250

Sample Output 4

5
29
91
572
28
25
33
103
82
73

Sample Input 5

1 4
1000 1000 9999
1000 1000 0
999 1000 0
0 0 1999
0 0 2000

Sample Output 5

9999
0
0
9999