Star sky

题意翻译

## 题目描述： 在空中设置笛卡尔坐标系。有 $n$ 个星星，第 $i$ 个星星有坐标 $(x_i,y_i)$ 和最大亮度 $c$ ，每个星星有个初始亮度 $s_i(0\leq s_i\leq c)$ 随着时间推移，星星的亮度也在变化。第0时刻亮度为 $s_i$ 。若 $t$ 时刻亮度为 $x$ ，则 $t+1$ 时刻为 $x+1,x+1\leq c$ 否则为0 你想观察天空 $q$ 次，第 $i$ 你会在 $t_i$ 时刻观察一个和坐标轴平行的矩阵范围，矩阵左下角为 $(x_{1i},y_{1i})$ ，右上角为 $(x_{2i},y_{2i})$ 。对于每一次观察，你都想知道范围内星星亮度总和 若星星在边界上也算作内部 ## 输入输出格式： ### 输入格式： 第一行三个整数 $n,q,c(1\leq n,q\leq 10^5,1\leq c\leq 10)$ 分别表示星星数量，看星星的次数，星星的最大亮度 接下来 $n$ 行，第 $i$ 行三个整数 $x_i,y_i,s_i(1\leq x_i,y_i\leq 100,0\leq s_i\leq c\leq 10)$ 表示第 $i$ 个星星的坐标和初始亮度 在接下来 $q$ 行，第 $i$ 行五个整数 $t_i,x_{1i},y_{1i},x_{2i},y_{2i}(0\leq t_i\leq 10^9,1\leq x_{1i}\lt x_{2i}\leq 100,1\leq y_{1i}\lt y_{2i}\leq 100)$ 分别表示观察时刻和矩阵坐标 ### 输出格式： 对于每次询问，输出星星亮度之和 感谢@Fheiwn 提供的翻译

题目描述

The Cartesian coordinate system is set in the sky. There you can see $ n $ stars, the $ i $ -th has coordinates ( $ x_{i} $ , $ y_{i} $ ), a maximum brightness $ c $ , equal for all stars, and an initial brightness $ s_{i} $ ( $ 0<=s_{i}<=c $ ). Over time the stars twinkle. At moment $ 0 $ the $ i $ -th star has brightness $ s_{i} $ . Let at moment $ t $ some star has brightness $ x $ . Then at moment $ (t+1) $ this star will have brightness $ x+1 $ , if $ x+1<=c $ , and $ 0 $ , otherwise. You want to look at the sky $ q $ times. In the $ i $ -th time you will look at the moment $ t_{i} $ and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates ( $ x_{1i} $ , $ y_{1i} $ ) and the upper right — ( $ x_{2i} $ , $ y_{2i} $ ). For each view, you want to know the total brightness of the stars lying in the viewed rectangle. A star lies in a rectangle if it lies on its border or lies strictly inside it.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ q $ , $ c $ ( $ 1<=n,q<=10^{5} $ , $ 1<=c<=10 $ ) — the number of the stars, the number of the views and the maximum brightness of the stars. The next $ n $ lines contain the stars description. The $ i $ -th from these lines contains three integers $ x_{i} $ , $ y_{i} $ , $ s_{i} $ ( $ 1<=x_{i},y_{i}<=100 $ , $ 0<=s_{i}<=c<=10 $ ) — the coordinates of $ i $ -th star and its initial brightness. The next $ q $ lines contain the views description. The $ i $ -th from these lines contains five integers $ t_{i} $ , $ x_{1i} $ , $ y_{1i} $ , $ x_{2i} $ , $ y_{2i} $ ( $ 0<=t_{i}<=10^{9} $ , $ 1<=x_{1i}&lt;x_{2i}<=100 $ , $ 1<=y_{1i}&lt;y_{2i}<=100 $ ) — the moment of the $ i $ -th view and the coordinates of the viewed rectangle.

输出格式

For each view print the total brightness of the viewed stars.

输入输出样例

输入样例 #1

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

输出样例 #1

3
0
3

输入样例 #2

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

输出样例 #2

3
3
5
0

说明

Let's consider the first example. At the first view, you can see only the first star. At moment $ 2 $ its brightness is $ 3 $ , so the answer is $ 3 $ . At the second view, you can see only the second star. At moment $ 0 $ its brightness is $ 0 $ , so the answer is $ 0 $ . At the third view, you can see both stars. At moment $ 5 $ brightness of the first is $ 2 $ , and brightness of the second is $ 1 $ , so the answer is $ 3 $ .