N개의 정수가 주어진다. 이때 특정 구간에 있는 수들을 동시에 더하거나, 특정 구간의 합을 구하는 연산을 수행해야 한다.

예를 들어 1, 2, 3, 4, 5라는 수가 있을 때, 2번째부터 4번째 수에 각각 3을 더하라는 명령이 들어오면 수열은 1, 5, 6, 7, 5가 된다.

이후 2번째부터 5번째까지의 합을 구하라고 한다면 5+6+7+5=23을 출력하면 된다.

데이터의 양과 쿼리의 개수가 매우 많고, 업데이트가 구간 단위로 일어나므로 이를 효율적으로 처리하는 프로그램을 작성하시오.

입력

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

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

셋째 줄부터 M+K개의 줄에 걸쳐 연산의 정보가 주어진다.

a가 0인 경우, b번째 수부터 c번째 수에 각각 d를 더한다는 의미이다. (1 ≤ b ≤ c ≤ N)

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

출력

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

합의 결과와 중간 과정의 값들이 64비트 정수형 범위를 사용할 수 있으므로 주의하시오.

제약 조건

1 ≤ N ≤ 100,000

1 ≤ M ≤ 100,000

1 ≤ K ≤ 100,000

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

-1,000,000 ≤ d ≤ 1,000,000 (구간에 더할 값)

예제 입력 1

5 2 2
1 2 3 4 5
0 2 4 3
1 2 5
0 3 5 -2
1 1 3

예제 출력 1

23
10