입고가 끝난 뒤의 선반

문제

한 물류 창고에는 일렬로 놓인 N개의 선반이 있다. 선반에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있으며, 각 선반에는 같은 종류의 상자가 정수 개수만큼 놓여 있다. 창고 관리자는 오늘의 입고 작업을 모두 마친 뒤, 여러 구간에 놓인 상자의 총개수를 확인하려 한다. 상자는 선반 사이에서 옮기지 않으며, 오늘은 출고 작업도 없다. 입고 작업은 모두 M개다. 작업 하나에는 두 선반 번호 l, r과 상자 수 c가 적혀 있다. 이 작업을 수행하면 l번부터 r번까지의 모든 선반에 각각 c개의 상자를 추가한다. 양 끝 선반도 작업 대상에 포함된다. 예를 들어 2번부터 4번 선반까지 각각 3개를 추가하는 작업은 창고 전체에 상자 9개를 추가한다. c개를 구간 전체에 나누어 놓는 작업이 아니라, 구간에 속한 선반마다 c개씩 추가하는 작업이다. 여러 입고 작업의 대상 구간은 서로 겹칠 수 있다. 한 선반이 여러 작업의 대상에 포함되면 해당 작업에서 추가하는 상자 수를 모두 더한다. 처음부터 상자가 없는 선반도 있을 수 있으며, 추가하는 상자 수가 0인 작업도 허용된다. 선반의 수용량에는 별도의 제한이 없으므로 입력에 적힌 작업은 언제나 전부 수행할 수 있다. 입고 작업이 하나도 없으면 처음 놓여 있던 상자 수가 그대로 유지된다. 입고가 모두 끝나면 Q개의 확인 요청을 처리한다. 요청 하나에는 두 선반 번호 a, b가 주어지며, a번부터 b번까지의 선반에 놓인 상자를 모두 합한 값을 답해야 한다. 모든 요청은 동일하게 최종 상태를 기준으로 하며, 요청을 처리하면서 상자를 추가하거나 제거하지 않는다. 요청 구간이 겹치거나 같은 요청이 반복되어도 각각 독립적으로 답한다. 합계가 0이면 0을 출력하며, 별도로 불가능한 요청은 주어지지 않는다. 초기 상자 수, 입고 작업, 확인 요청이 주어졌을 때 각 요청의 답을 입력 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 선반 수 N, 입고 작업 수 M, 확인 요청 수 Q가 주어진다. 둘째 줄에 초기 상자 수 A_1, A_2, ..., A_N이 주어진다. 다음 M개 줄에는 입고 작업을 나타내는 l, r, c가 주어진다. 그다음 Q개 줄에는 확인 요청을 나타내는 a, b가 주어진다.
모든 입력값은 정수이며 1 ≤ N ≤ 20,000, 0 ≤ M ≤ 5,000, 1 ≤ Q ≤ 5,000, 0 ≤ A_i ≤ 1,000,000, 1 ≤ l ≤ r ≤ N, 0 ≤ c ≤ 1,000,000, 1 ≤ a ≤ b ≤ N이다.

출력

각 확인 요청에 대한 상자 수의 합을 입력 순서대로 한 줄에 하나씩 출력한다. 합계는 32비트 정수 범위를 넘을 수 있다. 모든 요청은 최종 상태를 기준으로 하므로 별도의 동점 처리나 답이 없는 경우는 없다.

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

25
11
6

3 0 2
0 0 0
1 3
2 2

0
0

3 2 2
1000000 1000000 1000000
1 3 1000000
1 3 1000000
1 3
2 2

9000000
3000000

출처: Devin.KR 자체 제작