RMT 지하철 부하 검사

RMT(Rail Metro Transit)는 지하철을 특이하게 운영한다. 지하철역은 $1$번부터 $N$번까지 $N$개 있고, 노선은 $1$번부터 $M$번까지 $M$개 있다. 각 역은 정확히 한 노선에 속하고, 모든 노선에는 역이 하나 이상 있다.

노선은 순환한다. 역 $S$의 다음 역은 같은 노선에 속한 역 중에서 번호가 $S$보다 크면서 가장 작은 역이다. $S$가 그 노선에서 번호가 가장 큰 역이면, $S$의 다음 역은 그 노선에서 번호가 가장 작은 역이다.

RMT는 자원한 승객을 태우고 부하 검사를 한다. 검사를 시작하는 시점에 모든 역에 열차가 한 대씩 서 있고, $i$번 역의 열차에는 승객 $A_i$명이 타고 있다. 자원자는 검사가 끝날 때까지 자기가 탄 열차에서 내리지 않는다.

검사 동안 RMT는 행동 $Q$개를 순서대로 한다. 각 행동은 다음 둘 중 하나다.

• $l$번 역부터 $r$번 역까지 서 있는 열차에 탄 승객 수의 합을 조사한다.
• $x$번 노선을 운행한다. $x$번 노선의 열차는 모두 그 노선의 다음 역으로 간다.

조사가 나올 때마다 그 답을 구하라.

첫째 줄에 세 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. ($1 \le M \le N \le 150000$, $1 \le Q \le 150000$)

둘째 줄에 정수 $N$개 $L_1, L_2, \dots, L_N$이 주어진다. ($1 \le L_i \le M$) $L_i$는 $i$번 역이 속한 노선의 번호다. 모든 노선에는 역이 하나 이상 있다.

셋째 줄에 정수 $N$개 $A_1, A_2, \dots, A_N$이 주어진다. ($1 \le A_i \le 7000$) $A_i$는 검사를 시작할 때 $i$번 역에 있는 승객 수다.

다음 $Q$개의 줄에는 행동이 한 줄에 하나씩 다음 두 형식 중 하나로 주어진다.

• 1 l r: $l$번 역부터 $r$번 역까지 조사한다. ($1 \le l \le r \le N$)
• 2 x: $x$번 노선을 운행한다. ($1 \le x \le M$)

조사마다 그 답을 한 줄에 하나씩 출력한다.

첫 번째 예제의 노선도는 아래와 같다. 역은 $1$번부터 $5$번까지 있고, 역을 잇는 선에는 그 선이 속한 노선 번호를 적었다.

처음 각 역의 승객 수는 {1, 2, 3, 4, 5}이다. 첫 번째 조사의 답은 $1 + 2 + 3 + 4 + 5 = 15$이다.

1번 노선을 운행하면 각 역의 승객 수가 {3, 2, 1, 4, 5}로 바뀌므로, 두 번째 조사의 답은 $1 + 4 + 5 = 10$이다.

2번 노선을 운행하면 각 역의 승객 수가 {3, 5, 1, 2, 4}로 바뀌므로, 세 번째 조사의 답은 $3 + 5 + 1 = 9$이다.

두 번째 예제의 노선도는 아래와 같다. 역은 $1$번부터 $3$번까지 있고, 모든 선이 1번 노선에 속한다.

첫 번째 조사 직전 각 역의 승객 수는 {114, 101, 109}이다. 두 번째 조사 직전에는 {109, 114, 101}, 세 번째 조사 직전에는 {101, 109, 114}, 네 번째 조사 직전에는 {114, 101, 109}이다.