{"raw_statement":[{"iden":"statement","content":"有 $n$ 个变量 $x[1 \\sim n]$，初始值都为 0。\n\n依次给出 $m$ 个操作的信息，操作分为 2 种：\n\n- $(1, id, v)$: 代表将 $x[id]$ 的值加上 $v$；\n- $2$: 代表将所有变量的值乘 $2$；\n\n所有运算在 $(\\bmod \\ 10^4)$ 下执行，提示：模意义下的加减乘运算\n\n- 加：`c = (a + b) % mod`；\n- 减：`c = (a - b + mod) % mod`；\n- 乘：`c = a * b % mod`；\n\n现在给出一个操作序列，请问依次执行序列中的所有操作之后，每个变量的值是多少。\n\n具体的，操作序列以 $q$ 个区间 $[l[i], r[i]]$ 的形式给出，依次执行每个区间、每个区间按编号从小->大执行区间内的操作，即完整的操作序列为：\n\n- $l[1] \\sim r[1], l[2] \\sim r[2], l[3] \\sim r[3], \\ldots, l[q] \\sim r[q]$"},{"iden":"input","content":"第一行 $3$ 个整数 $n, m, q$，代表变量数量，操作数量，操作序列中区间数量。\n\n接下来 $m$ 行，每行 $3$ 个整数 $op, id, v$ 或者 $1$ 个整数 $op$，给出所有操作的信息。\n\n接下来 $q$ 行，每行 $2$ 个整数 $l[i], r[i]$ 代表一个操作区间。"},{"iden":"output","content":"输出一行 $n$ 个整数，代表所有操作执行完之后每个变量的值。"},{"iden":"note","content":"### 样例 3-8\n\n见附件。\n\n### 数据范围\n\n对于所有数据，$1 \\leq n, m, q \\leq 2 \\times 10^5, op = \\{1, 2\\}, 1 \\leq id \\leq n, 1 \\leq v \\leq 10^9$，假设 $m$ 种操作中第 1、2 种操作的总数为 $m_1, m_2$，满足 $m_1 + m_2 = m$。\n\n本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。\n\n| 子任务编号 | 分值 | 数据范围 | 特殊性质 | 子任务依赖 |\n|:------------:|:------:|:----------:|:----------:|:------------:|\n| 1          | 15   | $n, m, q \\leq 500$ |          |            |\n| 2          | 19   | $n, m, q \\leq 5000$ |          | 1          |\n| 3          | 11   | $n, m, q \\leq 2 \\times 10^5$ | $m_2 = 0$ |            |\n| 4          | 17   | $n, m, q \\leq 2 \\times 10^5$ | $m_1 = 1, m_2 = m - 1$ |            |\n| 5          | 17   | $n, m, q \\leq 2 \\times 10^5$ | $m_1 = m - 1, m_2 = 1$ |            |\n| 6          | 21   | $n, m, q \\leq 2 \\times 10^5$ |          | 1,2,3,4,5          |"}],"translated_statement":null,"sample_group":[["5 5 5\n2\n1 1 3\n2\n2\n1 3 3\n2 5\n1 2\n1 1\n2 2\n3 4","228 0 48 0 0"],["10 10 10\n1 4 1\n1 7 3\n1 4 5\n1 1 3\n2\n1 5 5\n2\n2\n1 8 2\n1 7 1\n1 8\n1 1\n7 8\n1 4\n8 9\n3 9\n2 10\n4 7\n3 6\n6 9","2536 0 0 8952 3560 0 6304 4674 0 0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}