5

지하철 연구

시간제한 : 5초

어떤 광역시에는 특이한 지하철 시스템이 운영되고 있다. n개의 역이 m개의 노선으로 연결되어 운영되고 있는데, 각 역은 1개의 노선에만 속하고, 각 노선에는 적어도 1개의 역으로 구성되어있으며, 각 노선은 원형으로 연결되어있다. 같은 노선의 어떤 s번 역의 다음 역 번호는 그 번호보다 크고, 그 노선의 가장 큰 번호 역 다음에는 가장 작은 번호의 역이 연결되어있다.

광역시 연구팀에서는 자원봉사자들을 이용해 지하철 노선 시스템의 운송량 테스트를 수행하고 있다. 각 i번 역에 Ai명의 승객들이 있는 상태에서 테스트가 시작되며, 자원봉사자들은 테스트가 수행되는 동안 자신이 담당하는 역을 떠나지 않는다.

광역시 연구팀에서는 테스트가 수행되는 과정에서 q개의 주문을 자원봉사자들에게 보낸다. 주문은 2가지로 이루어지는데, 그 중 한 가지는 i번부터 j번 역에 있는 모든 승객의 수를 계산하는 것이고, 다른 한 가지는 x번 노선의 지하철들을 모두 다음 역으로 이동시키는 것이다.

연구팀의 연구 수행을 도와보자.

입력형식

첫 줄에는 n, m, q가 공백을 두고 입력된다.([eqn: 1 LEQ m` LEQ n LEQ `150,000], [eqn: 1 LEQ q LEQ `150,000])

두 번째 줄에는 각 1부터 n번역이 속하는 각각의 라인이 공백을 두고 입력된다.

세 번째 줄에는 테스트를 시작할 때, 1번 역부터 n번 역까지 있는 승객의 수(Ai)가 공백을 두고 입력된다.([eqn: 1 LEQ A _{i} LEQ 7,000])

그 다음 q개의 줄에는 다음과 같은 형태로 연구팀의 주문이 입력된다.:

- 1 i j,([eqn: 1 LEQ i LEQ `j LEQ `n]) : i번 역부터 j번 역까지 모든 승객의 수를 출력

- 2 x, ([eqn: 1 LEQ x LEQ `m]) : x번 노선 전체를 한 역만큼 이동시킴

출력형식

연구팀의 주문에 따라 이동시키고 승객 수를 출력한다.

입출력 예시

입력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

출력1

15

10

9

설명 : 테스트가 처음 시작할 때의 상태는 다음과 같다.

처음 승객 수는 각 역별로, 1, 2, 3, 4, 5.

1 1 5 : 1번~5번 역 승객 수의 합 출력. 1+2+3+4+5 = 15

2 1 : 1번 노선이 한 칸 이동 하면 3, 2, 1, 4, 5. 으로 상태가 바뀜.

1 3 5 : 3~5번 역 승객 수의 합 출력. 1+4+5 = 10

2 2 : 2번 노선 한 칸 이동. 3, 5, 1, 2, 4 로 인원 수 바뀜.

1 1 3 : 1~3번 역 승객 수의 합 출력. 3+5+1 = 9

입력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

출력2

114

109

101

114