상영관 통로 점검표

문제

한 영화관은 긴 상영관 통로를 N개의 구역으로 나누고, 입구에서 가까운 순서대로 1번부터 N번까지 번호를 붙였다. 시설 담당자는 여러 차례 통로를 걸으며 바닥 조명을 점검했다. 한 번의 점검에서는 연속한 구역을 살펴보며, 점검표에는 그때 살펴본 첫 구역과 마지막 구역만 기록한다. 두 끝 구역도 해당 점검에 포함된다. 담당자는 각 구역을 몇 번 살펴보았는지 확인한 뒤, 점검 횟수가 K번 이상인 구역에 확인 표시를 하려고 한다. 같은 범위를 여러 번 점검했더라도 각 기록은 별개의 점검으로 센다. 점검표의 기록 순서는 횟수 계산에 영향을 주지 않는다. 어떤 점검에도 포함되지 않은 구역의 점검 횟수는 0번이다. 다음 상영 전에 안내판 하나를 설치할 예정이다. 안내판에는 확인 표시가 있는 구역만으로 이루어진 연속 구간 하나를 적을 수 있다. 선택한 구간의 중간에 확인 표시가 없는 구역이 하나라도 있으면 그 구간은 사용할 수 없다. 구간의 길이는 마지막 구역 번호에서 첫 구역 번호를 빼고 1을 더한 값이다. 구역 번호가 N번에서 1번으로 이어지는 것으로 취급하지는 않는다. 사용할 수 있는 구간 중 길이가 가장 긴 구간을 구한다. 가장 긴 구간이 여러 개라면 첫 구역 번호가 가장 작은 구간을 선택한다. 점검 횟수가 K번 이상인 구역이 하나도 없다면 선택할 수 있는 구간이 없는 것으로 처리한다. 점검 기록이 전혀 없거나 K가 전체 점검 횟수보다 클 수도 있다. 선택한 구간의 길이와 양 끝 구역 번호를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, K가 공백으로 주어진다. 1≤N≤200,000, 0≤M≤15,000, 1≤K≤15,001이다.
다음 M개 줄에는 한 번의 점검 범위를 나타내는 정수 L, R이 공백으로 주어진다. 1≤L≤R≤N이다. 같은 범위가 여러 번 주어질 수 있다.

출력

선택한 구간의 길이, 첫 구역 번호, 마지막 구역 번호를 공백으로 구분하여 한 줄에 출력한다. 선택할 수 있는 구간이 없으면 0 0 0을 출력한다.

10 4 2
1 5
3 7
6 9
4 6

5 3 7

5 2 3
1 5
1 5

0 0 0

7 2 1
1 2
5 6

2 1 2

출처: Devin.KR 자체 제작