RMT Subway Load Test

Rail Metro Transit (RMT) runs an unusual subway system. There are $N$ subway stations numbered from $1$ to $N$, and $M$ subway lines numbered from $1$ to $M$. Every station belongs to exactly one line, and every line has at least one station.

Each line is circular. For a station $S$, the next station after $S$ is the station of the same line whose number is the smallest among those larger than $S$. If $S$ already has the largest number among the stations of its line, the next station after $S$ is the station of that line with the smallest number.

RMT is running a load test with volunteer passengers. When the test starts, one train stands at every station, and the train at station $i$ carries $A_i$ passengers. The volunteers stay on their own train until the test ends.

During the test, RMT performs $Q$ actions in order. Each action is one of two kinds:

• a survey of the total number of passengers on the trains standing at stations $l$ through $r$,
• an operation of line $x$, which sends every train of line $x$ to the next station of that line.

Report the answer of every survey.

The first line contains three space separated integers $N$, $M$ and $Q$ ($1 \le M \le N \le 150000$, $1 \le Q \le 150000$).

The second line contains $N$ integers $L_1, L_2, \dots, L_N$ ($1 \le L_i \le M$), where $L_i$ is the line that station $i$ belongs to. Every line has at least one station.

The third line contains $N$ integers $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 7000$), the number of passengers at each station when the test starts.

Each of the next $Q$ lines holds one action in one of these two forms:

• 1 l r, a survey of stations $l$ through $r$ ($1 \le l \le r \le N$).
• 2 x, an operation of line $x$ ($1 \le x \le M$).

For every survey, print its answer on its own line.

The first example is drawn below. The stations are numbered from $1$ to $5$, and every connection carries the number of the line it belongs to.

At the start the passenger counts are {1, 2, 3, 4, 5}. The first survey answers $1 + 2 + 3 + 4 + 5 = 15$.

Operating line 1 changes the counts to {3, 2, 1, 4, 5}, so the second survey answers $1 + 4 + 5 = 10$.

Operating line 2 changes the counts to {3, 5, 1, 2, 4}, so the third survey answers $3 + 5 + 1 = 9$.

The second example is drawn below. The stations are numbered from $1$ to $3$, and every connection belongs to line 1.

Just before the first survey the counts are {114, 101, 109}. Just before the second survey they are {109, 114, 101}, just before the third survey {101, 109, 114}, and just before the fourth survey {114, 101, 109}.