게임 이용 구간의 청구액

문제

한 게임 서버의 백엔드는 이용 기록을 발생 순서대로 보관한다. 기록은 1번부터 N번까지 번호가 붙어 있으며, i번 기록의 기본 이용 요금은 A_i원이다. 기록 하나의 요금은 이미 확정되어 있으므로 청구서를 계산하는 동안 바뀌지 않는다. 무료 이용 기록도 보관하므로 기본 이용 요금이 0원일 수 있다. 운영 도구에서는 연속된 이용 기록을 묶어 청구액을 미리 확인한다. 청구 요청 하나는 세 정수 L, R, C로 주어진다. 이 요청은 L번부터 R번까지의 기록을 양 끝을 포함하여 선택하고, 액면가가 C원인 할인권 하나를 적용한다는 뜻이다. 선택한 모든 기본 이용 요금의 합을 S라고 한다. 할인권 사용 기준 H는 모든 요청에 공통으로 적용된다. 할인권을 사용할 수 있는지는 할인 전 합계 S로 판단한다. S가 H 이상이면 S와 C 중 작은 금액을 할인한다. S가 H보다 작으면 할인하지 않는다. 할인권을 사용하고 남은 잔액이나 할인권의 미사용 금액은 다른 요청에 전달하지 않는다. 따라서 할인 후 금액 B는 항상 0 이상의 정수이며, 액면가가 합계보다 크더라도 음수가 되지 않는다. 세금은 할인 후 금액 B의 10퍼센트이며, 원 미만은 버린다. 즉 세금은 B를 10으로 나눈 몫이고, 최종 청구액은 B와 세금의 합이다. 각 기록에 세금을 따로 계산해서 더하는 방식은 사용하지 않는다. 할인권을 사용할 수 없는 요청에도 같은 방식으로 세금을 계산한다. 모든 청구 요청은 원본 이용 기록을 대상으로 독립적으로 계산한다. 앞선 요청이 기록을 소비하거나 할인권의 적용 상태를 바꾸지 않는다. 요청이 입력된 순서대로 최종 청구액을 출력하는 프로그램을 작성한다. 선택한 기록이 모두 무료이거나 할인으로 금액이 전부 차감되면 청구액은 0원이다.

입력

첫째 줄에 정수 N, Q, H가 공백으로 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ Q ≤ 10,000, 1 ≤ H ≤ 1,000,000,000이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 0 ≤ A_i ≤ 99,999이다.
다음 Q개 줄에는 요청을 나타내는 정수 L, R, C가 공백으로 주어진다. 1 ≤ L ≤ R ≤ N, 0 ≤ C ≤ 1,000,000이다. 모든 금액의 단위는 원이다.

출력

각 요청의 최종 청구액을 입력 순서대로 한 줄에 정수 하나씩 출력한다.

5 4 100
40 60 15 0 85
1 2 30
3 4 50
2 5 200
5 5 10

77
16
0
93

3 3 1
0 0 10
1 2 100
3 3 0
1 3 9

0
11
1

출처: Devin.KR 자체 제작