Bajtazaurの森には、$10^6$ 本の木が一直線に並んでおり、1から $10^6$ まで順に番号が振られています。森の端、木番号1のすぐ手前にBajtazaurが住んでいます。

Bajtazaurはダイエットを決意し、健康的な生活を始めることにしました。彼は今後 $n$ 日間の計画を立てました。$i$ 日目には自宅から木番号 $a_i$ まで歩いて往復し、その道中で出会うすべての木からそれぞれ正確に $v_i$ 枚の葉を食べます。ただし、1回の散歩中に同じ木から葉を食べるのは1回だけです*。

当初、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$ 日間で、木番号 $d_j$ から合計で何枚の葉がBajtazaurに食べられるか？」というものです。

Bajtazaurの質問に答えてあげてください。

入力

入力の1行目には、3つの整数 $n, m, z$ ($1 \le n, m, z \le 10^6, n \cdot m \cdot z \le 10^{16}$) が含まれており、それぞれBajtazaurの計画の日数、修正の回数、質問の回数を表します。

2行目には、$n$ 個の整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^6$) が含まれており、各日にBajtazaurが散歩する先の木の番号を表します。

続く $m+z$ 行には、計画の修正内容またはBajtazaurの質問が1行ずつ記述されています。

• $j$ 回目の修正を表す行は、3つの整数 $1, p_j, w_j$ ($1 \le p_j \le n, 1 \le w_j \le 10^6$) で構成され、それぞれ日数と、Bajtazaurが食べる葉の量を増やす値を表します。
• $j$ 番目の質問を表す行は、3つの整数 $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$ 番目の質問に対する答え、すなわち、質問の時点で考慮されている計画の最初の $p_j$ 日間に、木番号 $d_j$ からBajtazaurが食べる葉の総数を出力してください。

*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

注記

例の解説：Bajtazaurの計画は3日間 ($n = 3$) です。Bajtazaurは初期計画に対して $m = 2$ 回の修正を行い、$z = 4$ 回の質問をします。

1日目の計画は木番号 $a_1 = 3$ への散歩、2日目は木番号 $a_2 = 4$、3日目は木番号 $a_3 = 1$ です。最初は $v_1 = v_2 = v_3 = 0$ であり、Bajtazaurは葉を食べる予定はありません。その後、Bajtazaurは修正を行い、質問をします。

• 2 3 1 – Bajtazaurは最初の3日間で木番号1から何枚の葉を食べるか質問します。答えは0です。まだ食べる予定がないためです。
• 1 2 10 – Bajtazaurは最初の2日間の $v_i$ の値を10増やします。この修正後、$v_1 = 10, v_2 = 10, v_3 = 0$ となります。
• 2 1 2 – Bajtazaurは最初の1日間で木番号2から何枚の葉を食べるか質問します。答えは10です。1日目の散歩先は $a_1 = 3$ であり、その道中に木番号2があるため、$v_1 = 10$ 枚の葉を食べます。
• 2 3 1 – Bajtazaurは最初の3日間で木番号1から何枚の葉を食べるか質問します。答えは20です。1日目に $v_1 = 10$ 枚、2日目に $v_2 = 10$ 枚、3日目に $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です。1日目に $v_1 = 11$ 枚、2日目に $v_2 = 11$ 枚食べ、3日目は木番号 $a_3 = 1$ への散歩のみなので、木番号2には立ち寄りません。

制約

以下の表において、$a \sim b$ は $0.99 \cdot b < a \le b$ を意味します。