题目描述

某气象台每天都要从遍布于各地的观察站采集气温数据，并通过互联网为远程用户提供统计查询服务。其中最常见的一类查询是，根据用户指定矩形区域内所有观察站的观测值计算出平均气温。随着更多观察站的不断建立，原始数据本身的规模急剧膨胀。另外，尽管可以假设每天采集的数据相对固定，但随着用户群体的扩大，查询的频率也日益激增。鉴于传统蛮力算法的效率已无法满足实用要求，气象台只好请你帮忙，通过改进数据结构和算法，提高查询的效率。

输入格式

第一行为两个整数：观察站总数 $n$，所需查询的总次数 $m$。

以下 $n$ 行分别描述各观察站：位置坐标为整数 $(x, y)$，该站所测得温度值为整数 $t$。

再以下 $m$ 行分别对应于各次查询操作，整数 $(x_1, y_1)$ 和 $(x_2, y_2)$ 分别表示其西南角和东北角。

输出格式

共 $m$ 行，各含 $1$ 个整数，表示每次查询所得平均温度。若查询区域不含任何观测站，则输出 $0$。

4 2
0 0 1000
1 1 1300
2 2 1600
3 3 1100
0 0 1 1
0 0 10 10

1150
1250

提示

$0 ≤n ≤ 50,000$，$0 ≤ m ≤ 500,000$，观测站坐标取值范围是 $[-2^{31}, 2^{31})$，查询区域的坐标 $x_1 ≤ x_2$ 且 $y_1 ≤ y_2$。