Migrated from Lutece 2550 魔空「小行星带」

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

???： 敢动一动我就射击了！ 雾雨魔理沙： 说错了。 敢射击就要动了，马上就动。 博丽灵梦: 啥？ 为什么在这个地方会有魔理沙？

幻想乡 119 季秋天，本应是满月的夜晚，月亮却有一点点瑕疵。人类或许难以察觉，但妖怪们却对此十分敏感。为了夺回幻想乡的满月，八云紫拉上博丽灵梦，停止了夜晚，并踏上了解决异变的道路。

在迷途竹林，两人（？）遭遇了同样是来调查异变的魔理沙并与其大打出手。

魔空「小行星带」是魔理沙在关卡中使用的第一张符卡，魔理沙将释放出铺天盖地的星星。假设有 $n$ 颗星，每颗星在平面直角坐标系上的坐标是 $x_i,y_i$，且每颗星有一个初始的亮度等级 $s_i$，该亮度等级会随时间的增加而变化，设 $t$ 时刻某颗星的亮度等级是 $x$，$t+1$ 时刻其亮度等级变为 $x+1$，但如果这颗星的亮度等级达到了一个上限 $c$，那么下一时刻它的亮度等级变为 $0$。

八云紫向蓝提出 $q$ 个询问，每个询问给出一个时间 $t_i$ 和两个点 $(x_1,y_1),(x_2,y_2)$。保证第一个点在第二个点的左下方，问在 $t_i$ 时刻，这两个点所确定的矩形（含边界）内所有星星的亮度等级之和是多少。然而蓝因为某些原因无法很快回答询问，所以就由你来写程序回答这些问题了。

Input

第一行 $n,q,c$ 三个数，表示总的星星数目，询问数和每个星星的最大亮度等级。 接下来 $n$ 行，每行三个数 $x_i,y_i,s_i$，表示这颗星星的坐标和初始亮度等级（时间从 $0$ 开始）。 再接下来 $q$ 行，每行五个数 $t_i,x_{1i},y_{1i},x_{2i},y_{2i}$，表示第 $q$ 个询问的时间和两个点的坐标。

Output

对每个询问，一行输出一个数表示答案。

Samples

2 3 3
1 1 1
3 2 0
2 1 1 2 2
0 2 1 4 5
5 1 1 5 5

3
0
3

Constraints

$1 \leqslant n \leqslant 5 \times 10^4$，$1 \leqslant q \leqslant 5 \times 10^4$，$1 \leqslant c \leqslant 10$ $1 \leqslant x_i \leqslant 10^6$，$1 \leqslant y_i \leqslant 10^6$，$0 \leqslant s_i \leqslant c$ $0 \leqslant t_i \leqslant 10^5$，$1 \leqslant x_{1i} \leqslant x_{2i} \leqslant 10^6$，$1 \leqslant y_{1i} \leqslant y_{2i} \leqslant 10^6$ 保证所有数据为正整数。 保证每个询问中的两个点不重合。 保证初始给的 $n$ 个点不重合。

Note

询问中所给的矩形可能会退化成线段。

Resources

2021 UESTC ICPC Training for Data Structures