题目描述

校园活动地图上有 $n$ 个展位，每个展位可以看作平面上的一个点。第 $i$ 个展位位于 $(x_i,y_i)$，并带有一个积分值 $p_i$。任意两个展位不会处在同一个坐标上。

老师会给出 $m$ 个与坐标轴平行的矩形区域。对每个区域，请统计落在该矩形内部或边界上的所有展位积分之和；如果区域内没有展位，则答案为 $0$。

输入格式

第一行包含两个整数 $n,m$，表示展位数量和查询次数。

接下来 $n$ 行，每行包含三个整数 $x_i,y_i,p_i$，表示一个展位的坐标和积分值。

接下来 $m$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一次查询矩形的两个对角坐标。保证矩形边与坐标轴平行。

输出格式

输出 $m$ 行，每行一个整数，表示对应查询的积分总和。

样例

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

数据范围

对于第 $1\sim2$ 个测试点，$1\le n,m\le 100$；

对于第 $3\sim5$ 个测试点，$1\le n\le 50000,1\le m\le 10000$；

对于第 $6\sim10$ 个测试点，$1\le n\le 100000,1\le m\le 100000$。

对于所有测试点，$-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$。