题目描述

到了晚上，Bessie 喜欢观察天上的星星。假定可以把天空看成一个直角坐标系，她可以观察到 \(n\) 颗星星，每颗星星有一坐标\((x_i,y_i)\)，另外有一个最大亮度值 \(c\)，所有星星的亮度均不超过 \(c\)。
星星是不停闪烁的，也就是说亮度总是随着时间变化而变化的。为了简化起见，我们假定星星的亮度值总是环形增加的，每颗星星在时间点为 \(0\) 时，亮度为初始值 \(s_i\)；在时间点 \(t\) 时，亮度值为 \(x\)，则下一个时间点 \(t+1\) 时，亮度值为 \(x+1\)
（当亮度值超过 \(c\) 时，继续从 \(0\) 开始，即 \(0->1->2->……->c-1->c->0\)）。
晚上，Bessie 观察了 \(q\) 次，第 \(i\) 次观察的时间点是 \(t_i\)，每次观察，她只能观察某一个矩形范围，其左下角坐标是\((x_{1i},y_{1i})\)，其右上角坐标是 \((x_{2i},y_{2i})\)。现在她想知道，她的每次观察中，那个矩形范围内所有星星的亮度总和。请你编程帮助她完成这个任务。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤ 10^4),q(≤10^5),c(≤10)\)，分别表示星星数、 观察次数和最大亮度；接下来 \(n\) 行， 每行三个整数：\(x_i,y_i(1≤x_i,y_i≤200),s_i(0≤s_i≤c)\)，分别表示星星的坐标和初始亮度值；接下来 \(q\) 行，每行五个整数：\(t_i(0≤t_i≤10^9),x_{1i},y_{1i},x_{2i},y_{2i}(1≤ x_{1i},y_{1i},x_{2i},y_{2i}≤200)\)，分别表示第 \(i\) 次观察的时间点、左下角坐标和右上角坐标。

输出格式

对于每组数据的每次观察，输出指定矩形内所有星星的亮度总和。

样例1

输入样例1

2   
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 4 5
1 1 2
2 3 0
3 3 1
0 1 1 100 100
1 2 2 4 4
2 2 1 4 7
1 50 50 51 51

输出样例1

3
0
3
3
3
5
0

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("star.in","r",stdin);
freopen("star.out","w",stdout);