题目描述

题目译自 PA 2025 Runda 5 Liście

在 Bajtocki 森林里，生长着 $10^6$ 棵树，排成一列，编号从 $1$ 到 $10^6$。Bajtazaur（形象如图所示，正走向森林中的树木）住在森林边缘的 $1$ 号树前。 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$，不吃叶子。
• 随后按顺序执行修改和提问：
  1. $2\ 3\ 1$：问前 $3$ 天从 $1$ 号树吃多少叶子。还未修改，吃 $0$ 片。
  2. $1\ 2\ 10$：修改前 $2$ 天，每棵树多吃 $10$ 片，更新为 $v_1=10, v_2=10, v_3=0$。
  3. $2\ 1\ 2$：问第 $1$ 天从 $2$ 号树吃多少。第 $1$ 天走到 $3$ 号树，经过 $2$ 号树，吃 $v_1=10$ 片。
  4. $2\ 3\ 1$：问前 $3$ 天从 $1$ 号树吃多少。第 $1$ 天吃 $v_1=10$ 片，第 $2$ 天吃 $v_2=10$ 片，第 $3$ 天吃 $v_3=0$ 片，总共 $20$ 片。
  5. $1\ 3\ 1$：修改前 $3$ 天，每棵树多吃 $1$ 片，更新为 $v_1=11, v_2=11, v_3=1$。
  6. $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$：