원형 눈금의 관측 기록

문제

한 천문대의 관측 장치에는 원형으로 배치된 M개의 눈금이 있다. 눈금에는 시계 방향으로 0부터 M−1까지 번호가 붙어 있으며, M−1번 눈금에서 시계 방향으로 한 칸 더 움직이면 0번 눈금에 도착한다. 장치는 처음에 0번 눈금을 가리킨다. 관측 담당자는 장치를 차례대로 회전시키며 N번의 관측을 진행한다. 각 관측 기록에는 회전량 D_i와 목표 눈금 T_i가 들어 있다. D_i가 양수이면 현재 위치에서 시계 방향으로 D_i칸 움직이고, 음수이면 반시계 방향으로 −D_i칸 움직인다. D_i가 0이면 움직이지 않는다. 회전량의 절댓값이 M 이상일 수도 있으며, 이때도 적힌 칸 수만큼 원을 따라 계속 움직인 것으로 처리한다. 회전이 끝난 위치는 다음 관측을 시작할 때의 위치가 된다. 장치는 정확히 목표 눈금을 가리키지 않아도 일정 범위 안에 있으면 관측에 성공한다. 두 눈금 사이의 원형 거리는 한 눈금에서 다른 눈금까지 시계 방향 또는 반시계 방향으로 움직일 때 필요한 칸 수 중 작은 값이다. i번째 회전을 모두 마친 뒤 장치가 가리키는 눈금과 T_i 사이의 원형 거리가 R 이하이면 i번째 관측은 성공이다. 거리가 정확히 R인 경우도 성공에 포함한다. 회전하는 도중 목표 눈금을 지났는지는 성공 여부에 영향을 주지 않는다. 담당자는 전체 성공 횟수와 가장 길게 연속하여 성공한 구간을 기록하려 한다. 연속 성공 구간은 관측 번호가 연속하고 그 안의 모든 관측이 성공인 구간이다. 길이가 같은 최장 구간이 여러 개라면 시작 관측 번호가 가장 작은 구간을 선택한다. 관측 번호는 1부터 시작한다. 관측에 한 번도 성공하지 않았다면 전체 성공 횟수와 최장 구간의 길이를 모두 0으로 기록하고, 구간의 시작 번호도 0으로 기록한다. 각 관측의 회전량과 목표 눈금이 주어졌을 때 전체 성공 횟수, 최장 연속 성공 구간의 길이, 선택한 구간의 시작 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 관측 횟수 N, 눈금 수 M, 성공 허용 거리 R이 공백으로 구분되어 주어진다. 다음 N개 줄 중 i번째 줄에 D_i와 T_i가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1≤N≤20,000, 2≤M≤360,000, 0≤R≤⌊M/2⌋, −360,000≤D_i≤360,000, 0≤T_i<M이다.

출력

전체 성공 횟수, 최장 연속 성공 구간의 길이, 그 구간의 시작 관측 번호를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 최장 구간이 여러 개이면 시작 번호가 가장 작은 것을 출력한다. 성공한 관측이 없으면 0 0 0을 출력한다.

4 12 1
2 3
4 8
-1 4
7 0

3 2 3

3 8 0
1 0
2 2
-3 1

0 0 0

5 10 0
-1 9
11 0
0 4
2 2
-2 0

4 2 1

출처: Devin.KR 자체 제작