← 返回题目列表

Codeforces · 835/C

C. 星空

中文机器翻译题面 查看原题

笛卡尔坐标系设置在天空中。在那里你可以看到 n 颗星星,第 i 个星星的坐标为 (xi, yi),所有星星的最大亮度为 c,初始亮度为 si (0 ≤ si ≤ c)。

随着时间的推移,星星闪烁。在时刻 0,第 i 颗恒星的亮度为 si。设在时刻 t 某颗恒星的亮度为 x。那么在时刻 (t + 1),如果 x + 1 ≤ c,则该恒星的亮度为 x + 1,否则为 0。

你想看天空 q 次。在第 i 次时,您将看到时刻 ti,您将看到一个边长与坐标轴平行的矩形,左下角的坐标为 (x1i, y1i),右上角的坐标为 (x2i, y2i)。对于每个视图,您想知道位于所查看矩形中的星星的总亮度。

如果一颗星位于矩形的边界上或严格位于矩形内部,则该星位于矩形内。

输入

第一行包含三个整数 n、q、c (1 ≤ n, q ≤ 105, 1 ≤ c ≤ 10) — 星星的数量、视图的数量和星星的最大亮度。

接下来的 n 行包含星星描述。这些行中的第 i 行包含三个整数 xi、yi、si(1 ≤ xi、yi ≤ 100、0 ≤ si ≤ c ≤ 10)——第 i 颗恒星的坐标及其初始亮度。

接下来的 q 行包含视图描述。这些行中的第 i 行包含五个整数 ti、x1i、y1i、x2i、y2i (0 ≤ ti ≤ 109, 1 ≤ x1i < x2i ≤ 100, 1 ≤ y1i < y2i ≤ 100) - 第 i 个视图的时刻和所查看矩形的坐标。

输出

对于每个视图,打印所查看星星的总亮度。

示例

输入 #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

注意

让我们考虑第一个例子。

在第一次查看时,您只能看到第一颗星星。在第 2 时刻,其亮度为 3,因此答案为 3。

在第二个视图中,您只能看到第二颗星星。在 0 时刻,其亮度为 0,因此答案为 0。

在第三个视图中,您可以看到两颗星星。在第5时刻,第一个的亮度是2,第二个的亮度是1,所以答案是3。