N - Building Construction Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

2 次元平面上に、各辺が x, y 軸に並行な正方形の敷地が N 個あり、i 個目の敷地の範囲は領域 xmin_i \leq x \leq xmin_i + D_i, ymin_i \leq y \leq ymin_i + D_i です。各敷地にはコストが定まっており、i 番目の敷地のコストは C_i です。

今、Q 件のビル建設計画があり、j 件目の計画での建設予定地点の座標は (A_j, B_j) です。

各計画のコストは、その計画の建設座標を含む (または境界線上に持つ) すべての敷地のコストの和です。

各計画のコストを求めてください。

制約

  • 1 \leq N \leq 50000
  • 1 \leq Q \leq 100000
  • -10^9 \leq xmin_i, ymin_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • 0 \leq C_i \leq 10^9
  • -10^9 \leq A_i, B_i \leq 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
xmin_1 ymin_1 D_1 C_1
xmin_2 ymin_2 D_2 C_2
:
xmin_N ymin_N D_N C_N
A_1 B_1
:
A_Q B_Q

出力

Q 行出力せよ。j 行目に j 件目の計画のコストを出力すること。

入力例 1

2 4
1 3 6 10
3 6 6 20
4 7
-1 -1
1 4
7 13

出力例 1

30
0
10
0
  • 1 件目の計画の座標は、1, 2 個目の敷地に含まれるので、10 + 20 = 30 を出力してください。
  • 2 件目の計画の座標は、どちらの敷地にも含まれないので、0 を出力してください。
  • 3 件目の計画の座標は、1 個目の敷地に含まれるので、10 を出力してください。
  • 4 件目の計画の座標は、どちらの敷地にも含まれないので、0 を出力してください。

入力例 2

2 3
-3 5 4 100
1 9 7 30
1 9
1 8
8 10

出力例 2

130
100
30
  • 1 件目の計画の座標は、1, 2 個目の敷地に含まれるので、100 + 30 = 130 を出力してください。
  • 2 件目の計画の座標は、1 個目の敷地に含まれるので、100 を出力してください。
  • 3 件目の計画の座標は、2 個目の敷地に含まれるので、30 を出力してください。

入力例 3

10 10
17 2 17 1000000000
7 12 12 1000000000
2 12 8 1000000000
2 12 2 1000000000
3 9 16 1000000000
8 13 15 1000000000
8 1 3 1000000000
15 9 17 1000000000
16 5 5 1000000000
13 12 9 1000000000
17 3
4 10
1 9
5 3
17 12
14 19
19 17
17 11
16 17
12 16

出力例 3

1000000000
1000000000
0
0
5000000000
4000000000
6000000000
3000000000
5000000000
3000000000

Score : 6 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In a two-dimensional plane, there are N square plots of land whose sides are parallel to the x- or y-axis. The i-th plot can be represented as the region xmin_i \leq x \leq xmin_i + D_i, ymin_i \leq y \leq ymin_i + D_i. Each of these plots has a fixed cost, and the cost of the i-th plot is C_i.

Here, Q construction plans are considered. The j-th plan aims to construct a building at coordinates (A_j, B_j).

The cost of each plan is the sum of the costs of all the plots covering (or touching) the construction point.

Find the cost of each plan.

Constraints

  • 1 \leq N \leq 50000
  • 1 \leq Q \leq 100000
  • -10^9 \leq xmin_i, ymin_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • 0 \leq C_i \leq 10^9
  • -10^9 \leq A_i, B_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
xmin_1 ymin_1 D_1 C_1
xmin_2 ymin_2 D_2 C_2
:
xmin_N ymin_N D_N C_N
A_1 B_1
:
A_Q B_Q

Output

Print Q lines. The j-th line should contain the cost of the j-th plan.

Sample Input 1

2 4
1 3 6 10
3 6 6 20
4 7
-1 -1
1 4
7 13

Sample Output 1

30
0
10
0
  • For the 1-st plan, both plots cover the construction point, so we should print 10 + 20 = 30.
  • For the 2-nd plan, neither plot covers the construction point, so we should print 0.
  • For the 3-rd plan, the 1-st plot covers the construction point, so we should print 10.
  • For the 4-th plan, neither plot covers the construction point, so we should print 0.

Sample Input 2

2 3
-3 5 4 100
1 9 7 30
1 9
1 8
8 10

Sample Output 2

130
100
30
  • For the 1-st plan, both plots cover the construction point, so we should print 100 + 30 = 130.
  • For the 2-nd plan, the 1-st plot covers the construction point, so we should print 100.
  • For the 3-rd plan, the 2-nd plot covers the construction point, so we should print 30.

Sample Input 3

10 10
17 2 17 1000000000
7 12 12 1000000000
2 12 8 1000000000
2 12 2 1000000000
3 9 16 1000000000
8 13 15 1000000000
8 1 3 1000000000
15 9 17 1000000000
16 5 5 1000000000
13 12 9 1000000000
17 3
4 10
1 9
5 3
17 12
14 19
19 17
17 11
16 17
12 16

Sample Output 3

1000000000
1000000000
0
0
5000000000
4000000000
6000000000
3000000000
5000000000
3000000000