题目描述

有 $n$ 个变量 $x[1 \sim n]$，初始值都为 0。

依次给出 $m$ 个操作的信息，操作分为 2 种：

• $(1, id, v)$: 代表将 $x[id]$ 的值加上 $v$；
• $2$: 代表将所有变量的值乘 $2$；

所有运算在 $(\bmod \ 10^4)$ 下执行，提示：模意义下的加减乘运算

• 加：c = (a + b) % mod；
• 减：c = (a - b + mod) % mod；
• 乘：c = a * b % mod；

现在给出一个操作序列，请问依次执行序列中的所有操作之后，每个变量的值是多少。

具体的，操作序列以 $q$ 个区间 $[l[i], r[i]]$ 的形式给出，依次执行每个区间、每个区间按编号从小->大执行区间内的操作，即完整的操作序列为：

• $l[1] \sim r[1], l[2] \sim r[2], l[3] \sim r[3], \ldots, l[q] \sim r[q]$

输入格式

第一行 $3$ 个整数 $n, m, q$，代表变量数量，操作数量，操作序列中区间数量。

接下来 $m$ 行，每行 $3$ 个整数 $op, id, v$ 或者 $1$ 个整数 $op$，给出所有操作的信息。

接下来 $q$ 行，每行 $2$ 个整数 $l[i], r[i]$ 代表一个操作区间。

输出格式

输出一行 $n$ 个整数，代表所有操作执行完之后每个变量的值。

5 5 5
2
1 1 3
2
2
1 3 3
2 5
1 2
1 1
2 2
3 4

228 0 48 0 0

10 10 10
1 4 1
1 7 3
1 4 5
1 1 3
2
1 5 5
2
2
1 8 2
1 7 1
1 8
1 1
7 8
1 4
8 9
3 9
2 10
4 7
3 6
6 9

2536 0 0 8952 3560 0 6304 4674 0 0

提示

样例 3-8

见附件。

数据范围

对于所有数据，$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$。

本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。