题目描述

在 Bajtocki 森林里，生长着 $10^{6}$ 棵树，排成一列，编号从 $1$ 到 $10^{6}$。森林边缘，就在 $1$ 号树前，住着 Bajtazaur。

Bajtazaur 决定减肥，开始运动生活。它为接下来的 $n$ 天制定了计划：第 $i$ 天，它会从家走到 $a_{i}$ 号树再返回，每棵经过的树吃掉正好 $v_{i}$ 片叶子，但每棵树在一次散步中只吃一次。

起初，Bajtazaur 雄心勃勃，设定每天的 $v_{i} = 0$，想完全不吃叶子。可它很快发现，这样饿肚子实在撑不下去，得慢慢调整吃的叶子数量。于是，它计划通过 $m$ 次修改调整方案：第 $j$ 次修改是将前 $p_{j}$ 天的 $v_{i}$ 增加 $w_{j}$ 片叶子，也就是对 $i = 1, 2, \ldots, p_{j}$，$v_{i}$ 增加 $w_{j}$。

在修改计划的间隙，Bajtazaur 会提出一些问题，总共 $z$ 个。第 $j$ 个问题是：在当前计划的前 $p_{j}$ 天，它总共会从 $d_{j}$ 号树吃掉多少叶子？

请你帮 Bajtazaur 回答这些问题。

输入格式

输入的第一行包含三个整数 $n, m, z$ $(1 \leq n, m, z \leq 10^{6}, n \cdot m \cdot z \leq 10^{16})$，分别表示 Bajtazaur 的减肥天数、计划修改次数和提问次数。

第二行包含 $n$ 个整数 $a_{1}, \ldots, a_{n}$ $(1 \leq a_{i} \leq 10^{6})$，表示每天 Bajtazaur 要走到的树编号。

接下来的 $m+z$ 行描述修改和提问，按时间顺序排列，每行一个描述：

• 三个整数 $1, p_{j}, w_{j}$ $(1 \leq p_{j} \leq n, 1 \leq w_{j} \leq 10^{6})$，表示将前 $p_{j}$ 天的吃叶量增加 $w_{j}$。
• 三个整数 $2, p_{j}, d_{j}$ $(1 \leq p_{j} \leq n, 1 \leq d_{j} \leq 10^{6})$，表示询问前 $p_{j}$ 天从 $d_{j}$ 号树吃的叶子总数。

这 $m+z$ 行中正好有 $m$ 次修改和 $z$ 次提问。回答问题时，只考虑提问前已执行的修改（输入中靠前的行），不考虑之后的修改（输入中靠后的行）。

输出格式

输出 $z$ 行，第 $j$ 行是一个整数，表示第 $j$ 个问题中，Bajtazaur 在提问时计划的前 $p_{j}$ 天从 $d_{j}$ 号树吃的叶子总数。

3 2 4
3 4 1
2 3 1
1 2 10
2 1 2
2 3 1
1 3 1
2 3 2

0
10
20
22

Bajtazaur 的计划有 $3$ 天（$n=3$），它会修改 $2$ 次（$m=2$），提问 $4$ 次（$z=4$）。

• 第 $1$ 天走到 3 号树（$a_{1}=3$），第 $2$ 天走到 $4$ 号树（$a_{2}=4$），第 $3$ 天走到 $1$ 号树（$a_{3}=1$）。
• 初始时 $v_{1}=v_{2}=v_{3}=0$，不吃叶子。

随后按顺序执行修改和提问：

• 2 3 1：问前 $3$ 天从 $1$ 号树吃多少叶子。还未修改，吃 $0$ 片。
• 1 2 10：修改前 $2$ 天，每棵树多吃 $10$ 片，更新为 $v_{1}=10, v_{2}=10, v_{3}=0$。
• 2 1 2：问第 $1$ 天从 $2$ 号树吃多少。第 $1$ 天走到 $3$ 号树，经过 $2$ 号树，吃 $v_{1}=10$ 片。
• 2 3 1：问前 $3$ 天从 $1$ 号树吃多少。第 $1$ 天吃 $v_{1}=10$ 片，第 $2$ 天吃 $v_{2}=10$ 片，第 $3$ 天吃 $v_{3}=0$ 片，总共 $20$ 片。
• 1 3 1：修改前 $3$ 天，每棵树多吃 $1$ 片，更新为 $v_{1}=11, v_{2}=11, v_{3}=1$。
• 2 3 2：问前 $3$ 天从 $2$ 号树吃多少。第 $1$ 天吃 $v_{1}=11$ 片，第 $2$ 天吃 $v_{2}=11$ 片，第 $3$ 天走到 $1$ 号树，不经过 $2$ 号树，总共 $22$ 片。

数据范围与提示

详细子任务附加限制及分值如下表所示。

其中 $a \sim b$ 表示 $0.99 \cdot b < a \leq b$：