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

1 2 3 4 . . .

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

Ocenianie

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