In the Bajtocki Forest, there are $10^6$ trees arranged in a row and numbered sequentially from 1 to $10^6$. At the edge of the forest, just before tree number 1, lives Bajtazaur.

Bajtazaur has decided to go on a diet and start a healthy lifestyle. He has prepared a plan for the next $n$ days: on the $i$-th day, he will take a walk from his home to tree number $a_i$ and back, eating exactly $v_i$ leaves from every tree he encounters, but only once from each tree during a single walk*.

Initially, Bajtazaur ambitiously decided that $v_i = 0$ for every $i$, but he quickly realized that he would likely not survive such a fast and should gradually adjust the amount of leaves he eats. Bajtazaur will fix his plan using $m$ modifications: the $j$-th modification will consist of increasing the number of leaves eaten by $w_j$ for the first $p_j$ days. In other words, for every $i = 1, 2, \dots, p_j$, the value $v_i$ will be increased by $w_j$.

From time to time, between performing modifications, Bajtazaur will ask questions. In total, he will ask $z$ questions, where the $j$-th one will be: how many leaves from tree number $d_j$ will be eaten by Bajtazaur in total during the first $p_j$ days of the current plan?

Help Bajtazaur and answer his questions.

Input

The first line of the input contains three integers $n$, $m$, and $z$ ($1 \le n, m, z \le 10^6$, $n \cdot m \cdot z \le 10^{16}$), representing, respectively: the number of days of Bajtazaur's planned diet, the number of modifications Bajtazaur will make, and the number of questions Bajtazaur needs answers to.

The second line contains a sequence of $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 10^6$), representing the numbers of the trees to which Bajtazaur will walk on individual days of the plan.

The next $m+z$ lines contain descriptions of plan modifications and Bajtazaur's questions, one description per line: A line describing the $j$-th plan modification consists of three integers $1$, $p_j$, $w_j$ ($1 \le p_j \le n$, $1 \le w_j \le 10^6$), representing, respectively, the number of days and the value by which Bajtazaur increases the number of leaves eaten. A line describing the $j$-th question consists of three integers $2$, $p_j$, $d_j$ ($1 \le p_j \le n$, $1 \le d_j \le 10^6$), representing, respectively, the number of days and the tree for which we need to calculate the eaten leaves.

Among these $m+z$ lines, there will be exactly $m$ modification descriptions and exactly $z$ question descriptions. The descriptions are given in chronological order, meaning that when answering a given question, one must include in the plan those modifications that were performed before the question was asked (i.e., they are given earlier in the input), while modifications that will be performed later (i.e., they are given later in the input) should not be included.

Output

The output should contain $z$ lines, and the $j$-th of them should contain the answer to the $j$-th question, i.e., the number of leaves that Bajtazaur will eat from tree number $d_j$ during the first $p_j$ days of the plan considered by Bajtazaur at the moment the question is asked.

*Bajtazaur figured out that on the way there he will only eat from trees with odd numbers, and on the way back he will only eat from trees with even numbers. In this way, he will distribute his meals evenly along the entire route.

Examples

Input 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

Output 1

0
10
20
22

Note

Explanation of the example: Bajtazaur's plan consists of three days ($n = 3$). Bajtazaur will perform $m = 2$ modifications to the initial plan and ask $z = 4$ questions.

On the first day, the plan provides for a walk to tree number $a_1 = 3$, on the second day to tree number $a_2 = 4$, and on the third day to tree number $a_3 = 1$. Initially $v_1 = v_2 = v_3 = 0$, which means Bajtazaur does not plan to eat any leaves. Then Bajtazaur performs modifications and asks questions:

• 2 3 1 – Bajtazaur asks how many leaves he will eat during the first 3 days of the plan from tree number 1 – the answer is 0, because Bajtazaur has not yet planned any eating.
• 1 2 10 – Bajtazaur modifies the plan by increasing the value of $v_i$ for the first 2 days by 10. After this modification we have: $v_1 = 10, v_2 = 10, v_3 = 0$.
• 2 1 2 – Bajtazaur asks how many leaves he will eat during only the first day of the plan from tree number 2 – the answer is 10, because on the first day during the walk to tree number $a_1 = 3$, he will eat $v_1 = 10$ leaves from tree number 2, which is on the way.
• 2 3 1 – Bajtazaur asks how many leaves he will eat during the first 3 days of the plan from tree number 1 – this time the answer is 20, because on the first day he will eat $v_1 = 10$ leaves, on the second day he will eat $v_2 = 10$ leaves, and on the third day he will eat $v_3 = 0$ leaves.
• 1 3 1 – Bajtazaur modifies the plan by increasing the value of $v_i$ for the first 3 days by 1. After this modification we have: $v_1 = 11, v_2 = 11, v_3 = 1$.
• 2 3 2 – Bajtazaur asks how many leaves he will eat during the first 3 days of the plan from tree number 2 – the answer is 22, because on the first day he will eat $v_1 = 11$ leaves, on the second day he will eat $v_2 = 11$ leaves, and on the third day he will go for a walk only to tree $a_3 = 1$, so he will not visit tree 2 at all.

Subtasks

In the table below, the notation $a \sim b$ means $0.99 \cdot b < a \le b$.