회의실 순환 보고서

문제

한 사무 공간의 회의실 관리자는 일정이 반복되는 N일짜리 운영 주기를 사용한다. 주기 안의 날짜에는 1번부터 N번까지 번호를 붙인다. N번 날짜가 끝나면 다음 주기의 1번 날짜가 이어진다. 관리자는 각 날짜에 회의실이 실제로 사용된 시간을 분 단위로 기록했고, 이 기록을 바탕으로 여러 구간의 이용 현황을 확인하려고 한다. 날짜 i의 사용 시간은 A_i분이다. 기록에는 회의가 겹친 시간이 없으며, 각 값은 0 이상 1,440 이하의 정수다. 사용 시간이 0분인 날짜를 완전히 비어 있는 날짜라고 부른다. 잠깐이라도 사용한 날짜는 완전히 비어 있는 날짜에 포함하지 않는다. 보고서에는 선택한 날짜들의 사용 시간 합계와 완전히 비어 있는 날짜 수를 함께 적는다. 보고서 요청은 시작 날짜 S와 끝 날짜 E로 주어진다. 날짜 번호가 증가하는 방향으로 S부터 E까지 이동하며 양 끝 날짜를 모두 포함한다. S가 E보다 작거나 같으면 S, S+1, ..., E를 포함한다. S가 E보다 크면 S부터 N까지의 날짜를 포함한 뒤 1로 돌아가 1부터 E까지의 날짜를 포함한다. 따라서 한 요청에 같은 날짜가 두 번 들어가는 일은 없다. 특히 S와 E가 같으면 해당 날짜 하루만 포함하며, 주기 전체를 뜻하지 않는다. 관리자는 같은 기록에 대해 Q개의 보고서를 요청한다. 요청을 처리하는 동안 날짜별 사용 시간은 바뀌지 않으며, 모든 요청은 서로 독립적이다. 어떤 요청의 보고서를 작성했다고 해서 해당 날짜의 사용 시간이 줄어들거나 다음 요청에서 제외되지는 않는다. 각 요청에 포함되는 날짜의 사용 시간 합계와 완전히 비어 있는 날짜 수를 입력 순서대로 출력하는 프로그램을 작성한다. 날짜별 회의 횟수나 빈 시간의 총합은 구할 필요가 없다.

입력

첫째 줄에 정수 N과 Q가 공백으로 주어진다. 1 ≤ N ≤ 40,000, 1 ≤ Q ≤ 12,000이다.
둘째 줄에 날짜별 사용 시간 A_1, A_2, ..., A_N이 공백으로 주어진다. 모두 정수이며 0 ≤ A_i ≤ 1,440이다.
다음 Q개 줄에 요청을 나타내는 정수 S와 E가 공백으로 주어진다. 1 ≤ S, E ≤ N이다.

출력

각 요청마다 사용 시간 합계와 완전히 비어 있는 날짜 수를 순서대로 공백으로 구분하여 한 줄에 출력한다. 총 Q개 줄을 출력하며 두 값은 모두 정수다.

5 4
0 30 0 75 15
2 4
4 2
3 3
1 5

105 1
120 1
0 1
120 2

1 2
1440
1 1
1 1

1440 0
1440 0

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

0 4
0 2
0 2

출처: Devin.KR 자체 제작