题目描述

在空中设置笛卡尔坐标系。有 $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)$ 分别表示观察时刻和矩阵坐标。

输出格式

对于每次询问，输出星星亮度之和。

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

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

3
3
5
0