在巴伊托克森林（Lesie Bajtockim）中，有 $10^6$ 棵樹排成一列，編號依序為 $1$ 到 $10^6$。巴伊塔龍（Bajtazaur）住在森林邊緣，就在編號 $1$ 的樹前面。

巴伊塔龍決定開始節食並過上運動生活。他為接下來的 $n$ 天制定了計畫：第 $i$ 天，他會從家裡走到編號 $a_i$ 的樹再走回來，並吃掉沿途遇到的每棵樹上恰好 $v_i$ 片葉子，但每次散步過程中，每棵樹他只會吃一次$^*$。

起初，巴伊塔龍雄心勃勃地設定 $v_i = 0$（對所有 $i$），但他很快意識到自己可能無法忍受這種飢餓，應該逐步調整吃葉子的數量。巴伊塔龍將透過 $m$ 次修改來修正他的計畫：第 $j$ 次修改是將前 $p_j$ 天的吃葉數量增加 $w_j$。換句話說，對於每個 $i = 1, 2, \dots, p_j$，值 $v_i$ 將增加 $w_j$。

有時，在執行修改的過程中，巴伊塔龍會提出問題。總共會有 $z$ 個問題，第 $j$ 個問題是：在當前計畫的前 $p_j$ 天內，巴伊塔龍總共會從編號 $d_j$ 的樹上吃掉多少片葉子？

請幫助巴伊塔龍回答他的問題。

輸入格式

輸入的第一行包含三個整數 $n, m, z$ ($1 \le n, m, z \le 10^6, n \cdot m \cdot z \le 10^{16}$)，分別代表巴伊塔龍計畫的總天數、修改次數以及他需要回答的問題數量。

第二行包含一個由 $n$ 個整數組成的序列 $a_1, \dots, a_n$ ($1 \le a_i \le 10^6$)，代表巴伊塔龍在計畫中各天會散步前往的樹的編號。

接下來的 $m+z$ 行包含計畫修改的描述以及巴伊塔龍的問題，每行一個描述： 描述第 $j$ 次計畫修改的行包含三個整數 $1, p_j, w_j$ ($1 \le p_j \le n, 1 \le w_j \le 10^6$)，分別代表天數以及巴伊塔龍增加吃葉數量的數值。 描述第 $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$ 個問題的回答，即在巴伊塔龍提出問題時，根據當前計畫，在前 $p_j$ 天內從編號 $d_j$ 的樹上吃掉的葉子總數。

$^*$巴伊塔龍想出了一個規則：去程時他只吃編號為奇數的樹，回程時他只吃編號為偶數的樹。透過這種方式，他將進食均勻地分佈在整條路線上。

範例

輸入 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

巴伊塔龍的計畫包含三天 ($n = 3$)。巴伊塔龍將對初始計畫進行 $m = 2$ 次修改，並提出 $z = 4$ 個問題。

第一天，計畫預計散步到編號 $a_1 = 3$ 的樹，第二天到 $a_2 = 4$，第三天到 $a_3 = 1$。起初 $v_1 = v_2 = v_3 = 0$，即巴伊塔龍不打算吃葉子。隨後巴伊塔龍執行修改並提出問題：

• 2 3 1 – 巴伊塔龍詢問前 3 天從編號 1 的樹上吃掉多少葉子 – 回答為 0，因為巴伊塔龍尚未計畫吃葉子。
• 1 2 10 – 巴伊塔龍修改計畫，將前 2 天的 $v_i$ 值增加 10。修改後：$v_1 = 10, v_2 = 10, v_3 = 0$。
• 2 1 2 – 巴伊塔龍詢問僅在計畫的第一天從編號 2 的樹上吃掉多少葉子 – 回答為 10，因為第一天散步到編號 $a_1 = 3$ 的樹時，他會吃掉沿途編號 2 的樹上的 $v_1 = 10$ 片葉子。
• 2 3 1 – 巴伊塔龍詢問前 3 天從編號 1 的樹上吃掉多少葉子 – 這次回答為 20，因為第一天吃 $v_1 = 10$ 片，第二天吃 $v_2 = 10$ 片，第三天吃 $v_3 = 0$ 片。
• 1 3 1 – 巴伊塔龍修改計畫，將前 3 天的 $v_i$ 值增加 1。修改後：$v_1 = 11, v_2 = 11, v_3 = 1$。
• 2 3 2 – 巴伊塔龍詢問前 3 天從編號 2 的樹上吃掉多少葉子 – 回答為 22，因為第一天吃 $v_1 = 11$ 片，第二天吃 $v_2 = 11$ 片，第三天只散步到編號 $a_3 = 1$ 的樹，因此根本不會造訪編號 2 的樹。

子任務

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