농장 출고 정산 구간

문제

농장의 주문 서버는 하루 동안 확정된 출고 항목을 접수 순서대로 저장한다. 각 항목에는 상품 한 개의 정가, 출고 수량, 할인율, 과세 여부가 기록되어 있다. 회계 담당자는 연속한 여러 항목을 하나의 정산 묶음으로 지정하여 청구 금액을 조회한다. 백엔드 개발자인 당신은 이미 확정된 출고 기록을 바탕으로 모든 조회에 응답해야 한다. 조회 사이에 기록이 추가되거나 수정되는 일은 없다. 할인은 각 항목의 상품 한 개에 먼저 적용한다. 정가가 p원이고 할인율이 d퍼센트이면 할인된 개당 가격은 p×(100-d)를 100으로 나눈 몫이다. 원 미만의 금액은 이 단계에서 버린다. 항목의 공급 금액은 이렇게 구한 개당 가격에 출고 수량을 곱한 값이다. 같은 항목의 전체 정가에 할인율을 적용한 뒤 버림하는 방식과는 결과가 다를 수 있으므로 계산 순서를 지켜야 한다. 과세 여부는 할인 계산에 영향을 주지 않는다. 조회에서 지정한 구간의 과세 항목 공급 금액 합을 T, 면세 항목 공급 금액 합을 E라고 하자. 이 정산 묶음의 세금은 T의 10퍼센트를 원 단위로 올림한 값이다. T가 0이면 세금도 0이다. 세금은 과세 항목마다 따로 구하지 않고, 구간의 과세 공급 금액을 모두 더한 뒤 단 한 번 계산한다. 최종 청구 금액은 T와 E와 세금을 더한 값이며, 별도의 배송비나 추가 할인은 없다. 조회마다 왼쪽 끝 항목 번호와 오른쪽 끝 항목 번호가 주어진다. 양 끝 항목을 모두 포함한 청구 금액을 입력된 조회 순서대로 출력한다. 서로 다른 조회의 구간이 겹쳐도 각 조회는 독립적이며, 이전 조회의 정산 결과가 다음 조회에 영향을 주지 않는다. 모든 금액과 수량은 정수로 처리한다.

입력

첫째 줄에 항목 수 N과 조회 수 Q가 주어진다. 1≤N,Q≤10,000이다.
다음 N개 줄에 항목 순서대로 정가 p, 수량 c, 할인율 d, 과세 표시 t가 주어진다. p,c,d,t는 정수이며 1≤p≤1,000,000, 1≤c≤100, 0≤d≤100, t∈{0,1}이다. t가 1이면 과세 항목이고 0이면 면세 항목이다.
다음 Q개 줄에 정수 l,r이 주어진다. 1≤l≤r≤N이다. 항목 번호는 1부터 시작한다.

출력

각 조회의 최종 청구 금액을 원 단위 정수로 한 줄에 하나씩 출력한다. 금액이 0이면 0을 출력한다. 답은 부호 있는 64비트 정수 범위에 들어간다.

3 3
105 2 10 1
50 3 0 0
19 1 0 1
1 3
1 1
2 2

378
207
150

2 2
9 1 0 1
500 4 100 0
1 2
2 2

10
0

출처: Devin.KR 자체 제작