{"raw_statement":[{"iden":"statement","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 _s__i_ (0 ≤ _s__i_ ≤ _c_).\n\nOver 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.\n\nYou 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.\n\nA star lies in a rectangle if it lies on its border or lies strictly inside it."},{"iden":"input","content":"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.\n\nThe 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.\n\nThe 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."},{"iden":"output","content":"For each view print the total brightness of the viewed stars."},{"iden":"examples","content":"Input\n\n2 3 3\n1 1 1\n3 2 0\n2 1 1 2 2\n0 2 1 4 5\n5 1 1 5 5\n\nOutput\n\n3\n0\n3\n\nInput\n\n3 4 5\n1 1 2\n2 3 0\n3 3 1\n0 1 1 100 100\n1 2 2 4 4\n2 2 1 4 7\n1 50 50 51 51\n\nOutput\n\n3\n3\n5\n0"},{"iden":"note","content":"Let's consider the first example.\n\nAt the first view, you can see only the first star. At moment 2 its brightness is 3, so the answer is 3.\n\nAt the second view, you can see only the second star. At moment 0 its brightness is 0, so the answer is 0.\n\nAt 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."}],"translated_statement":[{"iden":"statement","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] 颗星星的亮度为 #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]。\n\n你希望观察天空 #cf_span[q] 次。在第 #cf_span[i] 次观察时，你将在时刻 #cf_span[ti] 观察一个边与坐标轴平行的矩形区域，其左下角坐标为 (#cf_span[x1i], #cf_span[y1i])，右上角坐标为 (#cf_span[x2i], #cf_span[y2i])。对于每次观察，你希望知道位于该矩形区域内的星星的总亮度。\n\n若一颗星星位于矩形的边界上或严格在矩形内部，则认为它位于该矩形内。\n\n第一行包含三个整数 #cf_span[n], #cf_span[q], #cf_span[c]（#cf_span[1 ≤ n, q ≤ 105], #cf_span[1 ≤ c ≤ 10]）—— 分别表示星星数量、观察次数和星星的最大亮度。\n\n接下来的 #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] 颗星星的坐标及其初始亮度。\n\n接下来的 #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] 次观察的时刻及所观察矩形的坐标。\n\n对于每次观察，请输出所观察区域内星星的总亮度。\n\n考虑第一个例子：\n\n第一次观察时，你只能看到第一颗星星。在时刻 #cf_span[2]，其亮度为 #cf_span[3]，因此答案为 #cf_span[3]。\n\n第二次观察时，你只能看到第二颗星星。在时刻 #cf_span[0]，其亮度为 #cf_span[0]，因此答案为 #cf_span[0]。\n\n第三次观察时，你可以看到两颗星星。在时刻 #cf_span[5]，第一颗星星的亮度为 #cf_span[2]，第二颗星星的亮度为 #cf_span[1]，因此答案为 #cf_span[3]。"},{"iden":"input","content":"第一行包含三个整数 #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] 次观察的时刻及所观察矩形的坐标。"},{"iden":"output","content":"对于每次观察，请输出所观察区域内星星的总亮度。"},{"iden":"examples","content":"输入：\n2 3 3\n1 1 1\n3 2 0\n2 1 1 2 2\n0 2 1 4 5\n5 1 1 5 5\n\n输出：\n3\n0\n3\n\n输入：\n3 4 5\n1 1 2\n2 3 0\n3 3 1\n0 1 1 100 100\n1 2 2 4 4\n2 2 1 4 7\n1 50 50 51 51\n\n输出：\n3\n3\n5\n0"},{"iden":"note","content":"考虑第一个例子：\n\n第一次观察时，你只能看到第一颗星星。在时刻 #cf_span[2]，其亮度为 #cf_span[3]，因此答案为 #cf_span[3]。\n\n第二次观察时，你只能看到第二颗星星。在时刻 #cf_span[0]，其亮度为 #cf_span[0]，因此答案为 #cf_span[0]。\n\n第三次观察时，你可以看到两颗星星。在时刻 #cf_span[5]，第一颗星星的亮度为 #cf_span[2]，第二颗星星的亮度为 #cf_span[1]，因此答案为 #cf_span[3]。"}],"sample_group":[],"show_order":[],"formal_statement":"**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\\} \\} $ be the set of stars, where:  \n- $ x_i, y_i \\in \\mathbb{Z} $ are the Cartesian coordinates of star $ i $,  \n- $ s_i \\in \\{0, 1, \\dots, c\\} $ is its initial brightness.  \n\nLet $ Q = \\{ (t_j, x_{1j}, y_{1j}, x_{2j}, y_{2j}) \\mid j \\in \\{1, \\dots, q\\} \\} $ be the set of queries, where:  \n- $ t_j \\in \\mathbb{Z}_{\\geq 0} $ is the time of the $ j $-th observation,  \n- $ [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} $.  \n\n**Brightness Function**  \nFor a star $ i $ at time $ t $, its brightness is:  \n$$\nb_i(t) = (s_i + t) \\bmod (c + 1)\n$$\n\n**Constraints**  \n1. $ 1 \\leq n, q \\leq 10^5 $  \n2. $ 1 \\leq c \\leq 10 $  \n3. $ 1 \\leq x_i, y_i \\leq 100 $  \n4. $ 0 \\leq s_i \\leq c $  \n5. $ 0 \\leq t_j \\leq 10^9 $  \n6. $ 1 \\leq x_{1j} < x_{2j} \\leq 100 $, $ 1 \\leq y_{1j} < y_{2j} \\leq 100 $  \n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $, compute:  \n$$\n\\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)\n= \\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)\n$$","simple_statement":null,"has_page_source":false}