N개의 정수가 주어진다. 이때 중간에 수의 변경이 빈번히 일어나고, 그 중간에 어떤 부분의 합을 구하려 한다.

만약에 1, 2, 3, 4, 5라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 2+6+4+5=17을 출력하면 된다.

데이터의 양과 쿼리의 개수가 매우 많으므로, 이를 효율적으로 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 수의 변경이 일어나는 횟수 M, 구간의 합을 구하는 횟수 K가 공백을 사이에 두고 주어진다.

둘째 줄에는 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.

셋째 줄부터 M+K개의 줄에 걸쳐 세 정수 a, b, c가 주어진다.

a가 0인 경우, b번째 수를 c로 바꾼다는 의미이다. (1 ≤ b ≤ N)

a가 1인 경우, b번째 수부터 c번째 수까지의 합을 구하여 출력한다. (1 ≤ b ≤ c ≤ N)

출력

구간의 합을 구하는 연산(a가 1인 경우)에 대하여, 그 결과를 한 줄에 하나씩 출력한다.

제약 조건

1 ≤ N ≤ 100,000

1 ≤ M ≤ 100,000

1 ≤ K ≤ 100,000

-1,000,000,000 ≤ Ai ≤ 1,000,000,000

-1,000,000,000 ≤ c ≤ 1,000,000,000 (a=0인 경우 수의 변경 범위)

예제 입력 1

5 3 3
1 2 3 4 5
1 1 5
0 3 6
1 1 5
0 2 -2
1 1 3
0 1 10

예제 출력 1

15
18
5