Description

Input

The first line contains three integers $n$, $m$, and $q$ ($2 \le m \le n \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$) — the number of points, harbours, and queries, respectively.

The second line contains $m$ distinct integers $X_1, X_2, \ldots, X_m(1 \le X_i \le n)$ — the position at which the $i$-th harbour is located.

The third line contains $m$ integers $V_1, V_2, \ldots, V_m(1 \le V_i \le 10^7)$ — the value of the $i$-th harbour.

Each of the next $q$ lines contains three integers. The first integer is $t$ ($1\le t \le 2$) — type of query. If $t=1$, then the next two integers are $x$ and $v$ ($2 \le x \le n - 1$, $1 \le v \le 10^7$) — first-type query. If $t=2$, then the next two integers are $l$ and $r$ ($1 \le l \le r \le n$) — second-type query.

It is guaranteed that there is at least one second-type query.

Output

For every second-type query, print one integer in a new line — answer to this query.

8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8

171
0
15

Note

For the first type $2$ query, the cost for ships at positions $2$, $3$, $4$ and $5$ are $3(3 \times 1)$, $0$, $96(24 \times 4)$ and $72(24 \times 3)$ respectively.

For the second type $2$ query, since the ship at position $5$ is already at a harbour, so the cost is $0$.

For the third type $2$ query, the cost for ships at position $7$ and $8$ are $15(15 \times 1)$ and $0$ respectively.