Problem Description

Lao C is a programmer.

Recently, Lao C received a task from his boss—to develop a management system for mobile base stations in the city. As an experienced programmer, Lao C easily completed most of the system's functionalities and assigned one of them to you to implement.

Since the area of a base station is very small compared to the entire city, each base station can be considered as a point in the coordinate system, with its position represented by coordinates \((x, y)\). Additionally, each base station has many attributes, such as height, power, etc. Operators often define a region and query the information of all base stations within that region.

Now, you need to implement the functionality that, for a given rectangular region, returns the total power of all base stations within the region (including those on the boundary). If there are no base stations in the region, the answer should be \(0\).

Input Format

The first line contains two integers \(n, m\), representing the total number of base stations and the number of queries, respectively. The next \(n\) lines each contain three integers \(x_i, y_i, p_i\), separated by spaces, representing the coordinates \((x_i, y_i)\) and power \(p_i\) of a base station. No two base stations will be at the same coordinates.

The next \(m\) lines each contain four integers \(x_1, y_1, x_2, y_2\), separated by spaces, representing a query for a rectangular region. The diagonal coordinates of the rectangle are \((x_1, y_1)\) and \((x_2, y_2)\), and its sides are parallel to the coordinate axes.

Output Format

Output \(m\) lines, each containing a single integer corresponding to the result of each query.

Sample Input and Output

Input Sample #1

4 2
0 0 1
0 1 2
2 2 4
1 0 8
0 0 1 1
1 1 5 6

Output Sample #1

11
4

Input Sample #2

3 2
-100 0 16
1 -10 32
1000 100 64
0 0 0 1
-1000 -1000 10000 10000

Output Sample #2

0
112

Notes

For the first \(1\sim2\) test points, \(1 \leq n, m \leq 100\);

For the third \(3\sim5\) test points, \(1 \leq n \leq 50000, 1 \leq m \leq 10000\);

For the sixth \(6\sim10\) test points, \(1 \leq n \leq 100000, 1 \leq m \leq 100000\), with varying data complexity;

For all test points, \(-2^{31} \leq x_i, y_i, p_i, x_1, y_1, x_2, y_2 < 2^{31}, x_1 \leq x_2, y_1 \leq y_2\).

见题面 Input 部分

见题面 Output 部分