Problem Description

On a 2D plane, there are $ N $ square plots of land, each with sides parallel to the x and y axes. The range of the $ i $th plot is the region $xmin_i \leq x \leq xmin_i + D_i, ymin_i \leq y \leq ymin_i + D_i$. Each plot has a defined cost, with the cost of the $ i $th plot being $ C_i $.

There are $ Q $ building construction plans, where the coordinates of the planned construction site for the $ j $th plan are $ (A_j, B_j) $.

The cost of each plan is the sum of the costs of all plots that contain (or have the construction coordinates on their boundary) the planned construction coordinates.

Calculate the cost for each plan.

Input Format

The input is given from the 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 Format

Output $ Q $ lines. The $ j $th line should contain the cost of the $ j $th plan.

Sample Input and Output

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

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

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

Notes/Hints

Note

Discussion of this problem is prohibited until May 2, 2020, 18:00 JST. If mentioned, it may lead to claims for damages.

It is okay to publish the total score or certification level after the exam, but please refrain from disseminating information about which problems were solved.

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 inputs are integers

Sample Explanation 1

• The coordinates of the 1st plan are included in the 1st and 2nd plots, so output $ 10 + 20 = 30 $.
• The coordinates of the 2nd plan are not included in either plot, so output $ 0 $.
• The coordinates of the 3rd plan are included in the 1st plot, so output $ 10 $.
• The coordinates of the 4th plan are not included in either plot, so output $ 0 $.

Sample Explanation 2

• The coordinates of the 1st plan are included in the 1st and 2nd plots, so output $ 100 + 30 = 130 $.
• The coordinates of the 2nd plan are included in the 1st plot, so output $ 100 $.
• The coordinates of the 3rd plan are included in the 2nd plot, so output $ 30 $.

见题面 Input 部分

见题面 Output 部分