在 Bajtocki 森林中，有 $10^6$ 棵树排成一排，依次编号为 $1$ 到 $10^6$。在森林边缘，就在 $1$ 号树前，住着 Bajtazaur。

Bajtazaur 决定开始节食并开启运动生活方式。他制定了未来 $n$ 天的计划：第 $i$ 天，他会从家走到编号为 $a_i$ 的树再返回，吃掉沿途遇到的每棵树上恰好 $v_i$ 片叶子，但每次散步过程中每棵树只吃一次$^*$。

起初，Bajtazaur 雄心勃勃地决定对每个 $i$ 令 $v_i = 0$，但他很快意识到自己可能无法忍受这种饥饿，应该逐渐调整吃叶子的数量。Bajtazaur 将通过 $m$ 次修改来修正他的计划：第 $j$ 次修改包括将前 $p_j$ 天吃叶子的数量增加 $w_j$。换句话说，对于每个 $i = 1, 2, \dots, p_j$，值 $v_i$ 将增加 $w_j$。

有时，在执行修改的过程中，Bajtazaur 会提出问题。总共会提出 $z$ 个问题，第 $j$ 个问题是：在当前计划的前 $p_j$ 天内，Bajtazaur 总共会从编号为 $d_j$ 的树上吃掉多少片叶子？

请帮助 Bajtazaur 回答他的问题。

输入格式

输入的第一行包含三个整数 $n, m, z$ ($1 \le n, m, z \le 10^6, n \cdot m \cdot z \le 10^{16}$)，分别表示 Bajtazaur 计划的饮食天数、他将进行的修改次数以及他需要回答的问题数量。

第二行包含一个由 $n$ 个整数组成的序列 $a_1, \dots, a_n$ ($1 \le a_i \le 10^6$)，表示 Bajtazaur 在计划中各天散步前往的树的编号。

接下来的 $m+z$ 行包含计划修改的描述和 Bajtazaur 的问题描述，每行一个描述：

• 描述第 $j$ 次计划修改的行包含三个整数 $1, p_j, w_j$ ($1 \le p_j \le n, 1 \le w_j \le 10^6$)，分别表示天数以及 Bajtazaur 增加吃叶子数量的值。
• 描述第 $j$ 个问题的行包含三个整数 $2, p_j, d_j$ ($1 \le p_j \le n, 1 \le d_j \le 10^6$)，分别表示天数以及需要计算吃掉叶子数量的树。

在这 $m+z$ 行中，恰好包含 $m$ 个修改描述和 $z$ 个问题描述。这些描述按时间顺序给出，即在回答某个问题时，应考虑在提出该问题之前（即在输入中较早出现）执行的修改，而不应考虑稍后执行的修改（即在输入中较晚出现）。

输出格式

输出应包含 $z$ 行，第 $j$ 行应包含对第 $j$ 个问题的回答，即在 Bajtazaur 提出问题时，在所考虑计划的前 $p_j$ 天内，他从编号为 $d_j$ 的树上吃掉的叶子总数。

$^*$Bajtazaur 设想他在去程只吃编号为奇数的树，在回程只吃编号为偶数的树。这样他就能将进食均匀地分布在整个路线上。

样例

输入 1

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

输出 1

0
10
20
22

说明 1

Bajtazaur 的计划由三天组成 ($n = 3$)。Bajtazaur 将执行 $m = 2$ 次初始计划的修改并提出 $z = 4$ 个问题。

第一天，计划前往编号为 $a_1 = 3$ 的树，第二天前往 $a_2 = 4$，第三天前往 $a_3 = 1$。起初 $v_1 = v_2 = v_3 = 0$，即 Bajtazaur 不打算吃叶子。随后 Bajtazaur 执行修改并提出问题：

• 2 3 1 – Bajtazaur 询问前 3 天从 1 号树吃掉的叶子总数 – 回答为 0，因为 Bajtazaur 尚未计划进食。
• 1 2 10 – Bajtazaur 修改计划，将前 2 天的 $v_i$ 值增加 10。修改后：$v_1 = 10, v_2 = 10, v_3 = 0$。
• 2 1 2 – Bajtazaur 询问仅在第 1 天从 2 号树吃掉的叶子总数 – 回答为 10，因为第一天散步到 3 号树时，他会吃掉沿途 2 号树上的 $v_1 = 10$ 片叶子。
• 2 3 1 – Bajtazaur 询问前 3 天从 1 号树吃掉的叶子总数 – 此时回答为 20，因为第一天吃掉 $v_1 = 10$ 片，第二天吃掉 $v_2 = 10$ 片，第三天吃掉 $v_3 = 0$ 片。
• 1 3 1 – Bajtazaur 修改计划，将前 3 天的 $v_i$ 值增加 1。修改后：$v_1 = 11, v_2 = 11, v_3 = 1$。
• 2 3 2 – Bajtazaur 询问前 3 天从 2 号树吃掉的叶子总数 – 回答为 22，因为第一天吃掉 $v_1 = 11$ 片，第二天吃掉 $v_2 = 11$ 片，第三天他只散步到 $a_3 = 1$，所以根本不会访问 2 号树。

子任务

在下表中，记号 $a \sim b$ 表示 $0.99 \cdot b < a \le b$。