회의실 복도의 표시등

문제

한 건물의 회의실 관리자는 하루를 N개의 시간 칸으로 나누어 예약 현황을 확인한다. 시간 칸에는 하루의 시작부터 순서대로 1번부터 N번까지 번호가 붙어 있다. 예약 한 건에는 시작 시간 칸과 마지막 시간 칸이 적혀 있으며, 두 시간 칸을 모두 포함한 구간에서 회의실 하나를 사용한다. 모든 예약은 이미 승인되어 있으므로 예약을 취소하거나 시간을 옮기는 일은 없다. 회의실 복도에는 각 시간 칸의 혼잡 여부를 알려 주는 표시등이 있다. 어떤 시간 칸에서 진행되는 예약의 수가 기준값 K 이상이면 그 시간 칸의 표시등이 켜지고, K보다 작으면 꺼진다. 서로 다른 예약의 사용 구간이 겹치면 각각을 별도로 센다. 시작과 끝이 완전히 같은 예약이 여러 건 있어도 모두 다른 예약이며, 각 예약은 자신이 포함하는 모든 시간 칸의 예약 수를 1씩 늘린다. 관리자는 표시등이 중간에 한 번도 꺼지지 않고 연속으로 켜지는 구간을 찾으려 한다. 구간의 길이는 그 구간에 포함된 시간 칸의 개수다. 예를 들어 4번부터 6번까지 표시등이 켜져 있다면 이 구간의 길이는 3이다. 하루의 끝과 다음 날의 시작은 이어 붙이지 않으므로 N번 시간 칸과 1번 시간 칸은 연속한 것으로 취급하지 않는다. 표시등이 연속으로 켜지는 구간 중 길이가 가장 긴 구간의 길이와 시작 번호를 구한다. 가장 긴 구간이 여러 개라면 시작 번호가 가장 작은 구간을 선택한다. 표시등이 켜지는 시간 칸이 하나도 없다면 길이와 시작 번호를 모두 0으로 정한다. 예약이 없는 시간 칸의 예약 수는 0이며, 예약이 한 건도 없는 날에도 같은 규칙을 적용한다.

입력

첫째 줄에 시간 칸의 수 N, 예약의 수 M, 혼잡 기준 K가 공백으로 구분되어 주어진다.
다음 M개의 줄에는 각 예약의 시작 시간 칸 L과 마지막 시간 칸 R이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며 1 ≤ N ≤ 200,000, 0 ≤ M ≤ 20,000, 1 ≤ K ≤ 20,001, 1 ≤ L ≤ R ≤ N이다. 같은 예약 구간이 여러 번 주어질 수 있다.

출력

선택한 구간의 길이와 시작 번호를 공백으로 구분하여 한 줄에 출력한다. 표시등이 켜지는 시간 칸이 없다면 0 0을 출력한다.

10 4 2
1 4
3 7
6 9
8 10

4 6

7 3 2
1 3
2 2
5 7

1 2

5 0 1

0 0

출처: Devin.KR 자체 제작