Old C is a programmer. Recently, Old C received a task from his boss: to manage the mobile base stations in the city. As an experienced programmer, Old C easily completed most of the system's functions and has left one of them for you to implement.
Since the area of a base station is very small compared to the city's area, each base station can be viewed as a point in a coordinate system, and its position can be represented by $(x, y)$. In addition, each base station has many attributes, such as height, power, etc. Operators often define a region and query information about all base stations in that region.
The function you need to implement is: for a given rectangular region, calculate the sum of the power of all base stations in that region (including those on the boundary). If there are no base stations in the region, output 0.
Input
The first line contains two integers $n$ and $m$, representing the total number of base stations and the number of queries, respectively.
Next, there are $n$ lines, each containing three space-separated integers $x_i, y_i, p_i$, representing the coordinates $(x_i, y_i)$ and power $p_i$ of a base station. No two base stations are at the same coordinate.
Next, there are $m$ lines, each containing four space-separated integers $x1_j, y1_j, x2_j, y2_j$, representing a query rectangular region. The rectangle is defined by the coordinates $(x1_j, y1_j)$ and $(x2_j, y2_j)$, and its sides are parallel to the coordinate axes.
Output
Output $m$ lines, each containing one integer, corresponding to the result of each query.
Constraints
- For test cases 1–2: $1 \le n, m \le 100$;
- For test cases 3–5: $1 \le n \le 50000$, $1 \le m \le 10000$;
- For test cases 6–10: $1 \le n \le 100000$, $1 \le m \le 100000$;
- For all test cases: $-2^{31} \le x_i, y_i, p_i, x1_j, y1_j, x2_j, y2_j < 2^{31}$, $x1_j \le x2_j$, $y1_j \le y2_j$.
Examples
Input 1
4 2 0 0 1 0 1 2 2 2 4 1 0 8 0 0 1 1 1 1 5 6
Output 1
11 4
Input 2
3 2 -100 0 16 1 -10 32 1000 100 64 0 0 0 1 -1000 -1000 10000 10000
Output 2
0 112