헬스장 이용 내역 정산

문제

한 헬스장의 백엔드 서버가 이용 내역을 정산한다. 서버에는 발생 순서대로 번호가 붙은 N개의 이용 내역이 저장되어 있다. 각 내역에는 할인 전 공급가액이 원 단위의 정수로 기록되어 있다. 이용 내역의 번호는 1부터 N까지이며, 금액이 같은 내역도 서로 다른 내역으로 취급한다. 정산 요청 하나에는 시작 번호 L, 끝 번호 R, 할인율 D가 들어 있다. 이 요청은 L번부터 R번까지의 모든 이용 내역을 양 끝을 포함하여 하나의 계산서로 묶는다는 뜻이다. 먼저 해당 내역들의 할인 전 공급가액을 모두 더하여 S를 구한다. 다음으로 할인액을 S×D÷100의 소수점 이하를 버린 정수로 계산한다. 할인 후 공급가액 B는 S에서 이 할인액을 뺀 값이다. 마지막으로 세액을 B÷10의 소수점 이하를 버린 정수로 계산하고, B와 세액을 더한 값을 최종 청구액으로 삼는다. 반드시 합산, 할인액 계산, 할인액 차감, 세액 계산의 순서로 처리한다. 각 내역에 할인을 따로 적용한 뒤 더하거나, 각 내역의 세액을 먼저 구해서 더하는 방식은 사용하지 않는다. 모든 금액이 음수가 아니므로 소수점 이하를 버리는 연산은 정수 나눗셈으로 처리할 수 있다. 할인율이 100이면 할인 후 공급가액과 세액은 모두 0이다. 여러 정산 요청이 같은 내역을 포함할 수 있지만, 각 요청은 서로 독립적인 조회이다. 한 요청을 처리해도 저장된 금액은 바뀌지 않으며, 다른 요청의 계산에도 영향을 주지 않는다. 요청에 포함되는 내역은 항상 하나 이상이고, 취소 내역이나 추가 수수료는 없다. 주어진 순서대로 모든 요청의 최종 청구액을 계산하는 프로그램을 작성한다. 출력에서는 통화 기호와 천 단위 구분 기호를 사용하지 않는다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1≤N≤20,000, 1≤Q≤10,000이다.
둘째 줄에 각 내역의 할인 전 공급가액 A_1, …, A_N이 주어진다. 모든 A_i는 정수이며 0≤A_i≤9,999이다.
다음 Q개 줄에는 정산 요청을 나타내는 정수 L, R, D가 주어진다. 1≤L≤R≤N, 0≤D≤100이다.

출력

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

4 3
101 99 200 50
1 2 15
2 4 10
3 3 100

187
346
0

3 3
0 1 9
1 1 0
2 3 5
3 3 50

0
11
5

출처: Devin.KR 자체 제작