Problem Description

Translated from CCC2017 Senior T5 "RMT"

The RMT subway system operates an unusual network. There are $N$ subway stations numbered from $1$ to $N$, and $M$ subway lines numbered from $1$ to $M$. Each station belongs to exactly one line, and each line passes through at least one station. The subway network is circular. That is, if there is a station numbered $S$, the next station on the same line is the one with the next higher number. Unless $S$ is the highest numbered station on its line, in which case, the next station is the lowest numbered station on the same line.

RMT is conducting a load test with volunteers on their system. The test starts with a subway train at each station, and for each $i$, there are $A_i$ volunteers on the test train at station $i$. Volunteers will not leave their respective trains during the test.

During the test, RMT will perform $Q$ operations, each of which is either a query for the number of volunteers on the subway from station $l$ to station $r$, or an operation to run all trains on line $x$. When a train runs on line $x$, it moves to the next station on that line.

You are a die-hard fan of RMT and have volunteered to assist them with the operations and report the results.

Input Format

The first line contains three integers, $N$, $M$, and $Q$ ($1 \le M \le N \le 150,000; 1 \le Q \le 150,000$).

The second line contains $N$ integers $L_1, L_2, \dots, L_N$, representing the line number to which each station belongs.

The third line contains $N$ integers $A_1, A_2, \dots, A_N$, representing the initial number of volunteers at each station.

The following $Q$ lines each contain one of the following forms:

• 1 l r, indicating a query ($1 \le l \le r \le N$).
• 2 x, indicating that RMT will run all trains on line $x$ ($1 \le x \le M$).

Output Format

For each query, output a single line containing the answer to the query.

Sample Input and Output

Sample Input #1

5 2 5
1 2 1 2 2
1 2 3 4 5
1 1 5
2 1
1 3 5
2 2
1 1 3

Sample Output #1

15
10
9

Sample Input #2

3 1 7
1 1 1
114 101 109
1 1 1
2 1
1 1 1
2 1
1 1 1
2 1
1 1 1

Sample Output #2

114
109
101
114

Notes/Hints

Sample Explanation 1

The subway system is illustrated below, with stations numbered from $1$ to $5$, connected by lines numbered $1$ or $2$:

Initially, the number of volunteers at each station is $\{1, 2, 3, 4, 5\}$.

The first query's answer is $1 + 2 + 3 + 4 + 5 = 15$.

After running line $1$, the number of volunteers at each station becomes $\{3, 2, 1, 4, 5\}$.

The second query's answer is $1 + 4 + 5 = 10$.

After running line $2$, the number of volunteers at each station becomes $\{3, 5, 1, 2, 4\}$.

The third query's answer is $3 + 5 + 1 = 9$.

Sample Explanation 2

The subway system is illustrated below, with stations numbered from $1$ to $3$, connected only by line $1$:

Before the first query, the number of volunteers at each station is $\{114, 101, 109\}$.

Before the second query, the number of volunteers at each station is $\{109, 114, 101\}$.

Before the third query, the number of volunteers at each station is $\{101, 109, 114\}$.

Before the fourth query, the number of volunteers at each station is $\{114, 101, 109\}$.

For $\frac{2}{15}$ of the data, $N \le 1,000, Q \le 1,000$.

For another $\frac{2}{15}$ of the data, $L_i \le L_{i+1}$ ($1 \le i < N$).

For another $\frac{3}{15}$ of the data, $M \le 200$.

For another $\frac{3}{15}$ of the data, the number of stations on each line does not exceed $200$.

见题面 Input 部分

见题面 Output 部分