Description

Old C is a programmer.

Recently, Old C received a task from his boss — to write a management system for mobile base stations in the city. As an experienced programmer, Old C easily completed most of the system and left one feature for you to implement.

Since the area covered by one base station is very small compared to the whole city, each base station can be regarded as a point in the coordinate plane, with its position represented by coordinates $(x,y)$. In addition, each base station has many attributes, such as height and power. The operator often specifies a region and queries the information of all base stations in that region.

Your task is: for a given rectangular region, answer the sum of the power values of all base stations inside the region (including those on the boundary). If the region contains no base stations, output $0$.

Input Format

The first line contains two integers $n,m$, meaning there are $n$ base stations and $m$ queries. The next $n$ lines each contain three space-separated integers $x_i,y_i,p_i$, representing a base station at coordinates $(x_i,y_i)$ with power $p_i$. No two base stations share the same coordinates.

Then follow $m$ lines, each containing four space-separated integers $x_1,y_1,x_2,y_2$, denoting one query rectangle. The rectangle has diagonally opposite corners at $(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 one integer, the answer for the corresponding query.

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

11
4

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

0
112

Hint

For testdata $1 \sim 2$, $1 \le n,m \le 100$.

For testdata $3 \sim 5$, $1 \le n \le 50000$, $1 \le m \le 10000$.

For testdata $6 \sim 10$, $1 \le n \le 100000$, $1 \le m \le 100000$, and the testdata has a gradient.

For all testdata, $-2^{31} \le x_i,y_i,p_i,x_1,y_1,x_2,y_2 < 2^{31}$, $x_1 \le x_2$, $y_1 \le y_2$.

Translated by ChatGPT 5