구간 합 구하기 2

수 N개가 한 줄로 놓여 있다. 이 수열에 두 종류의 연산이 순서대로 들어온다. 하나는 어떤 구간에 속한 모든 수에 같은 값을 더하는 연산이고, 다른 하나는 어떤 구간에 속한 수를 모두 더한 값을 구하는 연산이다.

수열이 1, 2, 3, 4, 5인 경우를 보자. 3번째부터 4번째 수에 6을 더하면 수열은 1, 2, 9, 10, 5가 되고, 2번째부터 5번째까지의 합은 26이다. 이어서 1번째부터 3번째 수에 -2를 더하면 수열은 -1, 0, 7, 10, 5가 되고, 2번째부터 5번째까지의 합은 22이다.

연산을 입력에 나온 순서대로 처리해서, 합을 구하는 연산마다 그 값을 출력하라.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000), 수를 변경하는 연산의 횟수 M(1 ≤ M ≤ 10,000), 구간의 합을 구하는 연산의 횟수 K(1 ≤ K ≤ 10,000)가 공백으로 구분되어 주어진다.

둘째 줄부터 N개 줄에 수열의 값이 앞에서부터 한 줄에 하나씩 주어진다.

그다음 M+K개 줄에는 연산이 한 줄에 하나씩 주어진다. 줄이 1 b c d 형태이면 b번째 수부터 c번째 수까지 모두에 d를 더한다. 줄이 2 b c 형태이면 b번째 수부터 c번째 수까지의 합을 구한다. 두 형태 모두 1 ≤ b ≤ c ≤ N이다.

입력으로 주어지는 모든 수는 $-2^{63}$ 이상 $2^{63}-1$ 이하의 정수이다.

합을 구하는 연산마다 그 구간의 합을 한 줄에 하나씩, 입력에 나온 순서대로 출력한다. 출력하는 값은 모두 $-2^{63}$ 이상 $2^{63}-1$ 이하이다.