矩形求和

【题目描述】

二维平面上有 $N$ 个带权点。第 $i$ 个点的坐标为 $(x_i, y_i)$，权值为 $w_i$。 现在依次处理 $Q$ 个查询。

• $l$ $d$ $r$ $u$：求所有满足 $l \leq x < r$，$d \leq y < u$ 的点的权值之和。

【输入】

$N$ $Q$
$x_0$ $y_0$ $w_0$
$x_1$ $y_1$ $w_1$
:
$x_{N - 1}$ $y_{N - 1}$ $w_{N - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

【输出】

对每个查询输出一行一个整数，表示满足条件的点的权值之和。

【输入样例】

5 5
0 0 1
3 0 10
1 4 100
2 2 1000
3 2 10000
0 0 4 5
0 0 4 4
3 0 4 3
2 0 4 3
1 2 2 4

【输出样例】

11111
11011
10010
11010
0

【数据范围】

• $1 \leq N, Q \leq 200,000$
• $0 \leq x_i, y_i, w_i \leq 10^9$
• $0 \leq l_i < r_i \leq 10^9$
• $0 \leq d_i < u_i \leq 10^9$

【来源】

Library Checker（yosupo06） rectangle_sum