English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
For each view print the total brightness of the viewed stars.
[samples]
## Note
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.
在天空中建立了笛卡尔坐标系。你可以看到 #cf_span[n] 颗星星，第 #cf_span[i] 颗星星的坐标为 (#cf_span[xi], #cf_span[yi])，所有星星的最大亮度均为 #cf_span[c]，初始亮度为 #cf_span[si]（#cf_span[0 ≤ si ≤ c]）。
随着时间推移，星星会闪烁。在时刻 #cf_span[0]，第 #cf_span[i] 颗星星的亮度为 #cf_span[si]。设在时刻 #cf_span[t] 某颗星星的亮度为 #cf_span[x]，则在时刻 #cf_span[(t + 1)]，该星星的亮度为 #cf_span[x + 1]（若 #cf_span[x + 1 ≤ c]），否则为 #cf_span[0]。
你希望观察天空 #cf_span[q] 次。在第 #cf_span[i] 次观察时，你将在时刻 #cf_span[ti] 观察一个边与坐标轴平行的矩形区域，其左下角坐标为 (#cf_span[x1i], #cf_span[y1i])，右上角坐标为 (#cf_span[x2i], #cf_span[y2i])。对于每次观察，你希望知道位于该矩形区域内的星星的总亮度。
若一颗星星位于矩形的边界上或严格在矩形内部，则认为它位于该矩形内。
第一行包含三个整数 #cf_span[n], #cf_span[q], #cf_span[c]（#cf_span[1 ≤ n, q ≤ 105], #cf_span[1 ≤ c ≤ 10]）—— 分别表示星星数量、观察次数和星星的最大亮度。
接下来的 #cf_span[n] 行描述星星。第 #cf_span[i] 行包含三个整数 #cf_span[xi], #cf_span[yi], #cf_span[si]（#cf_span[1 ≤ xi, yi ≤ 100], #cf_span[0 ≤ si ≤ c ≤ 10]）—— 第 #cf_span[i] 颗星星的坐标及其初始亮度。
接下来的 #cf_span[q] 行描述观察。第 #cf_span[i] 行包含五个整数 #cf_span[ti], #cf_span[x1i], #cf_span[y1i], #cf_span[x2i], #cf_span[y2i]（#cf_span[0 ≤ ti ≤ 109], #cf_span[1 ≤ x1i < x2i ≤ 100], #cf_span[1 ≤ y1i < y2i ≤ 100]）—— 第 #cf_span[i] 次观察的时刻及所观察矩形的坐标。
对于每次观察，请输出所观察区域内星星的总亮度。
考虑第一个例子：
第一次观察时，你只能看到第一颗星星。在时刻 #cf_span[2]，其亮度为 #cf_span[3]，因此答案为 #cf_span[3]。
第二次观察时，你只能看到第二颗星星。在时刻 #cf_span[0]，其亮度为 #cf_span[0]，因此答案为 #cf_span[0]。
第三次观察时，你可以看到两颗星星。在时刻 #cf_span[5]，第一颗星星的亮度为 #cf_span[2]，第二颗星星的亮度为 #cf_span[1]，因此答案为 #cf_span[3]。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[q], #cf_span[c]（#cf_span[1 ≤ n, q ≤ 105], #cf_span[1 ≤ c ≤ 10]）—— 分别表示星星数量、观察次数和星星的最大亮度。接下来的 #cf_span[n] 行描述星星。第 #cf_span[i] 行包含三个整数 #cf_span[xi], #cf_span[yi], #cf_span[si]（#cf_span[1 ≤ xi, yi ≤ 100], #cf_span[0 ≤ si ≤ c ≤ 10]）—— 第 #cf_span[i] 颗星星的坐标及其初始亮度。接下来的 #cf_span[q] 行描述观察。第 #cf_span[i] 行包含五个整数 #cf_span[ti], #cf_span[x1i], #cf_span[y1i], #cf_span[x2i], #cf_span[y2i]（#cf_span[0 ≤ ti ≤ 109], #cf_span[1 ≤ x1i < x2i ≤ 100], #cf_span[1 ≤ y1i < y2i ≤ 100]）—— 第 #cf_span[i] 次观察的时刻及所观察矩形的坐标。
## Output
对于每次观察，请输出所观察区域内星星的总亮度。
[samples]
## Note
考虑第一个例子：
第一次观察时，你只能看到第一颗星星。在时刻 #cf_span[2]，其亮度为 #cf_span[3]，因此答案为 #cf_span[3]。
第二次观察时，你只能看到第二颗星星。在时刻 #cf_span[0]，其亮度为 #cf_span[0]，因此答案为 #cf_span[0]。
第三次观察时，你可以看到两颗星星。在时刻 #cf_span[5]，第一颗星星的亮度为 #cf_span[2]，第二颗星星的亮度为 #cf_span[1]，因此答案为 #cf_span[3]。
**Definitions**
Let $ n, q, c \in \mathbb{Z}^+ $ denote the number of stars, number of queries, and maximum brightness, respectively.
Let $ S = \{ (x_i, y_i, s_i) \mid i \in \{1, \dots, n\} \} $ be the set of stars, where:
- $ x_i, y_i \in \mathbb{Z} $ are the Cartesian coordinates of star $ i $,
- $ s_i \in \{0, 1, \dots, c\} $ is its initial brightness.
Let $ Q = \{ (t_j, x_{1j}, y_{1j}, x_{2j}, y_{2j}) \mid j \in \{1, \dots, q\} \} $ be the set of queries, where:
- $ t_j \in \mathbb{Z}_{\geq 0} $ is the time of the $ j $-th observation,
- $ [x_{1j}, x_{2j}] \times [y_{1j}, y_{2j}] $ is the axis-aligned rectangular region observed, with $ x_{1j} < x_{2j} $, $ y_{1j} < y_{2j} $.
**Brightness Function**
For a star $ i $ at time $ t $, its brightness is:
$$
b_i(t) = (s_i + t) \bmod (c + 1)
$$
**Constraints**
1. $ 1 \leq n, q \leq 10^5 $
2. $ 1 \leq c \leq 10 $
3. $ 1 \leq x_i, y_i \leq 100 $
4. $ 0 \leq s_i \leq c $
5. $ 0 \leq t_j \leq 10^9 $
6. $ 1 \leq x_{1j} < x_{2j} \leq 100 $, $ 1 \leq y_{1j} < y_{2j} \leq 100 $
**Objective**
For each query $ j \in \{1, \dots, q\} $, compute:
$$
\text{Answer}_j = \sum_{\substack{i=1 \\ x_{1j} \leq x_i \leq x_{2j} \\ y_{1j} \leq y_i \leq y_{2j}}}^{n} b_i(t_j)
= \sum_{\substack{i=1 \\ x_{1j} \leq x_i \leq x_{2j} \\ y_{1j} \leq y_i \leq y_{2j}}}^{n} \left( (s_i + t_j) \bmod (c + 1) \right)
$$
API Response (JSON)
{
"problem": {
"name": "C. Star sky",
"description": {
"content": "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 _",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF835C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 _...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在天空中建立了笛卡尔坐标系。你可以看到 #cf_span[n] 颗星星，第 #cf_span[i] 颗星星的坐标为 (#cf_span[xi], #cf_span[yi])，所有星星的最大亮度均为 #cf_span[c]，初始亮度为 #cf_span[si]（#cf_span[0 ≤ si ≤ c]）。\n\n随着时间推移，星星会闪烁。在时刻 #cf_span[0]，第 #cf_span[i] 颗星星...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q, c \\in \\mathbb{Z}^+ $ denote the number of stars, number of queries, and maximum brightness, respectively. \nLet $ S = \\{ (x_i, y_i, s_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ b...",
"is_translate": false,
"language": "Formal"
}
]
}