说明 笛卡尔坐标系（直角坐标系）设置在天空中。 在那里你可以看到 n 颗星星编号从1到n，第 i 个星星的坐标为 ( x i , y i ) (x i ​ ,y i ​ )，最大亮度 c，初始亮度 s i ( 0 ≤ s i ≤ c ) s i ​ (0≤s i ​ ≤c)。

随着时间的流逝，星星闪烁。 在 0 时刻，第 i 颗星的亮度为 s i s i ​ 。 让在 t 时刻，某颗星星的亮度为 x。 然后在时刻 (t + 1)，如果 x + 1 ≤ c，则该星星的亮度为 x + 1，否则为 0。

你想看天空q次。 在第 i 次时，您将查看时刻 t i t i ​ ，您将看到一个边平行于坐标轴的矩形，左上角的坐标为 ( x 1 i , y 1 i ) (x 1i ​ ,y 1i ​ )，右下角为 ( x 2 i , y 2 i ) (x 2i ​ ,y 2i ​ )。 对于每次查询，您想知道位于查看矩形中的星星的总亮度。

如果星星位于矩形的边界上或严格位于矩形内部，则它位于矩形中。

输入格式 第一行包含三个整数 n, q, c ( 1 ≤ n , q ≤ 1 0 5 , 1 ≤ c ≤ 10 ) (1≤n,q≤10 5 ,1≤c≤10)——星星的数量、观看次数和星星的最大亮度。

接下来的 n 行包含星星描述。 这些行中的第 i 个包含三个整数 x i , y i , s i ( 1 ≤ x i , y i ≤ 100 , 0 ≤ s i ≤ c ≤ 10 ) x i ​ ,y i ​ ,s i ​ (1≤x i ​ ,y i ​ ≤100,0≤s i ​ ≤c≤10)——第 i 颗星的坐标及其初始亮度。

接下来的 q 行包含查询描述。 这些行中的第 i 个包含五个整数 t i , x 1 i , y 1 i , x 2 i , y 2 i ( 0 ≤ t i ≤ 1 0 9 , 1 ≤ x 1 i < x 2 i ≤ 100 , 1 ≤ y 1 i < y 2 i ≤ 100 ) t i ​ ,x 1i ​ ,y 1i ​ ,x 2i ​ ,y 2i ​ (0≤t i ​ ≤10 9 ,1≤x 1i ​ <x 2i ​ ≤100,1≤y 1i ​ <y 2i ​ ≤100)表示第i个查询的时刻和被查看矩形的坐标。

输出格式 对于每次查询，输出所观察星星的总亮度。