CF835C.Star sky

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_1_i, y_1_i) and the upper right — (x_2_i, y_2_i). 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.

在天空中建立了笛卡尔坐标系。在那里可以看到 $n$ 颗恒星，其中第 $i$ 颗恒星的坐标为 $(x_i, y_i)$，最大亮度为 $c$（所有恒星相同），初始亮度为 $s_i$（满足 $0 \leq s_i \leq c$）。

随着时间推移，恒星会闪烁。在时刻 $0$，第 $i$ 颗恒星的亮度为 $s_i$。设某颗恒星在时刻 $t$ 的亮度为 $x$，则在时刻 $t+1$，其亮度为：若 $x+1 \leq c$，则为 $x+1$；否则为 $0$。

你希望观测天空 $q$ 次。在第 $i$ 次观测中，你将在时刻 $t_i$ 观测一个边与坐标轴平行的矩形区域，该矩形左下角坐标为 $(x_{1i}, y_{1i})$，右上角坐标为 $(x_{2i}, y_{2i})$。对每次观测，你需要计算位于该矩形区域内的所有恒星的亮度总和。

一颗恒星位于矩形内，当且仅当它位于该矩形的边界上或严格位于其内部。

The first line contains three integers n, q, c (1 ≤ n, q ≤ 105, 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_1_i, y_1_i, x_2_i, y_2_i (0 ≤ t__i ≤ 109, 1 ≤ x_1_i < x_2_i ≤ 100, 1 ≤ y_1_i < y_2_i ≤ 100) — the moment of the i-th view and the coordinates of the viewed rectangle.

第一行包含三个整数 $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} < x_{2i} \leq 100$，$1 \leq y_{1i} < y_{2i} \leq 100$）—— 表示第 $i$ 次观测的时刻以及所观测矩形区域的坐标。

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

对每个视角，输出所见恒星的总亮度。

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.

我们来考虑第一个例子。

在第一次观测时，你只能看到第一颗恒星。在时刻 2，它的亮度为 3，因此答案是 3。

在第二次观测时，你只能看到第二颗恒星。在时刻 0，它的亮度为 0，因此答案是 0。

在第三次观测时，你能同时看到两颗恒星。在时刻 5，第一颗恒星的亮度为 2，第二颗恒星的亮度为 1，因此答案是 3。