서버의 초과 요청 보고서

문제

게임 서버 운영자는 하루의 관측 시간을 같은 길이의 N개 구간으로 나누고, 각 구간에 도착한 요청 수를 기록했다. 관측 구간에는 시간순으로 1번부터 N번까지 번호가 붙어 있다. 서버의 기준 처리량은 모든 구간에서 동일한 정수 C다. 운영자는 이 기록을 바탕으로 여러 시간 범위의 초과 요청 보고서를 만들려고 한다. 한 관측 구간의 요청 수가 C보다 크면 그 구간을 초과 구간이라고 부른다. 초과 구간의 초과 요청 수는 실제 요청 수에서 C를 뺀 값이다. 요청 수가 C 이하인 구간의 초과 요청 수는 0이다. 특히 요청 수가 C와 정확히 같은 구간은 초과 구간에 포함되지 않는다. 보고서 작성 요청 하나에는 두 구간 번호 L과 R이 주어진다. 이 요청에 대해서는 L번부터 R번까지 양 끝을 모두 포함한 범위를 살펴본다. 보고서에는 범위 안의 초과 구간 수와 각 구간의 초과 요청 수를 모두 더한 값을 순서대로 적어야 한다. 두 값은 각각 구간의 개수와 요청의 개수를 나타내므로 서로 다른 값이다. 한 구간에서 남은 처리 여유를 다른 구간으로 옮길 수는 없다. 따라서 범위 전체의 요청 수에서 범위 전체의 기준 처리량을 빼는 방식으로 초과 요청 수를 구해서는 안 된다. 초과 여부와 초과 요청 수는 반드시 각 구간에서 따로 판단한 뒤 합산한다. 이전 구간에서 발생한 초과 요청이 다음 구간으로 이월되는 일도 없다. 모든 보고서는 처음 주어진 동일한 기록을 사용하며, 보고서를 작성하는 동안 요청 수나 기준 처리량은 바뀌지 않는다. 범위 안에 초과 구간이 하나도 없으면 보고서의 두 값은 모두 0이다. 관측 기록과 Q개의 작성 요청이 주어질 때, 각 보고서에 들어갈 두 정수를 입력된 순서대로 구한다.

입력

첫째 줄에 정수 N, Q, C가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 10,000, 1 ≤ Q ≤ 10,000, 0 ≤ C ≤ 1,000이다.
둘째 줄에 각 구간의 요청 수 A1, A2, ..., AN이 주어진다. 모든 Ai는 0 이상 1,000 이하의 정수다.
다음 Q개 줄에는 정수 L과 R이 주어진다. 각 요청은 1 ≤ L ≤ R ≤ N을 만족한다.

출력

각 작성 요청마다 초과 구간 수와 초과 요청 수의 합을 공백으로 구분하여 한 줄에 출력한다. 총 Q개 줄을 입력된 요청 순서대로 출력한다.

6 4 5
3 8 5 9 0 7
1 6
2 4
3 3
5 6

3 9
2 7
0 0
1 2

3 3 0
0 2 1
1 1
1 3
2 3

0 0
2 3
2 3

출처: Devin.KR 자체 제작