항공권 구간 판매 장부

문제

한 항공권 판매 창구는 N일 동안의 판매 내역을 날짜 순서대로 보관한다. 날짜에는 1부터 N까지 번호가 붙어 있다. 각 날짜의 기록에는 일반 항공권 판매 수와 할인 항공권 판매 수가 각각 적혀 있다. 두 판매 수는 모두 0 이상 9 이하의 정수다. 판매가 없었던 날도 기록에서 빠지지 않으며, 그날의 두 판매 수는 모두 0이다. 일반 항공권 한 장의 판매 금액은 3단위이고 할인 항공권 한 장의 판매 금액은 2단위다. 이 금액은 모든 날짜에 동일하게 적용된다. 장부에는 실제로 판매가 완료된 항공권만 기록되어 있으며, 취소나 환불은 없다. 따라서 어떤 기간의 판매 금액은 그 기간에 판매한 일반 항공권 수에 3을 곱한 값과 할인 항공권 수에 2를 곱한 값을 더하여 구한다. 창구 담당자는 서로 다른 기간을 대상으로 Q개의 조회를 요청했다. 각 조회에는 시작 날짜 L과 끝 날짜 R이 주어지며, L일과 R일을 모두 포함하는 기간을 살펴본다. 조회 결과에는 해당 기간에 판매한 전체 항공권 수와 해당 기간의 전체 판매 금액이 필요하다. 전체 항공권 수를 구할 때는 일반 항공권과 할인 항공권을 구분하지 않고 모두 더한다. 조회 기간은 서로 겹칠 수 있고, 같은 기간이 여러 번 주어질 수도 있다. 조회는 장부를 수정하지 않으므로 다른 조회의 결과에 영향을 주지 않는다. 기간의 길이가 하루인 조회와 전체 N일을 포함하는 조회도 허용된다. 조회 기간에 판매가 전혀 없다면 항공권 수와 판매 금액은 모두 0이다. 장부와 모든 조회를 입력받아 각 조회의 결과를 주어진 순서대로 출력하는 프로그램을 작성하라. 각 조회는 정해진 기간의 합계를 묻기 때문에 별도의 동점 처리는 없다.

입력

첫째 줄에 정수 N과 Q가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000이고 1 ≤ Q ≤ 10,000이다.
다음 N개 줄의 i번째 줄에 i일의 일반 항공권 판매 수 A_i와 할인 항공권 판매 수 B_i가 주어진다. A_i와 B_i는 0 이상 9 이하의 정수다.
다음 Q개 줄에 조회의 시작 날짜 L과 끝 날짜 R이 주어진다. L과 R은 정수이며 1 ≤ L ≤ R ≤ N이다.

출력

각 조회마다 전체 항공권 수와 전체 판매 금액을 공백으로 구분하여 한 줄에 출력한다. 조회가 주어진 순서를 지켜 총 Q개 줄을 출력한다.

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

7 17
0 0
9 22

1 2
0 9
1 1
1 1

9 18
9 18

출처: Devin.KR 자체 제작