시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 8 7 (88%) 7
문제
최근 백주부의 요리 TV가 인기이다. 이 TV 프로그램에서는 세계에 한국 요리의 즐거움을 소개한다. 첫 화에서는, 마스터 쉐프가 세계에서 가장 긴 $L$ 미터의 김밥을 만들었다. 그는 몇 시간 동안 고생을 한 후, $N$명의 분위기를 이끄는 방청객들에게 보상을 하기로 하였다. 그는 김밥을 $1$미터 길이로 자르고, 각각에 $1$부터 $L$까지 순서대로 번호를 매겼다. 각각의 방청객들은 $1$부터 $N$까지 고유 번호가 적힌 종이를 갖고 있고, 그 종이에는 추가적으로 두 숫자 $P$, $K$가 써져 있다. 각각의 방청객은 $P$번 김밥부터 $K$번 김밥까지 모두 가져갈 수 있는데, 이 때 고유 번호 순서대로 김밥을 가져간다. 이 순서 때문에, 어떤 방청객은 자기가 가져갈 것이라 예상했던 김밥의 수보다 더 적은 수의 김밥을 가져갈 수도 있다. 예를 들어, 1번 예제를 표현하면 아래와 같다. ``` 김밥 위치 1 2 3 4 5 6 7 8 9 10 고유 번호 1 1 1 3 2 2 3 ``` 이 때, 가장 많은 김밥을 가져갈 것으로 **예상하는** 방청객과, 가장 많은 김밥을 **실제로** 가져간 방청객을 알아내자.
입력
첫 번째 줄에 김밥의 길이 $L$이 주어진다. $(1 \le L \le 1\,000)$ 두 번째 줄에 방청객의 수 $N$이 주어진다. $(1 \le N \le 1\,000)$ 세 번째 줄부터 $N$개의 줄에 걸쳐, $i$번 고유 번호를 가진 방청객이 받은 숫자 $P_i$와 $K_i$가 공백으로 분리되어 주어진다. $(1 \le P_i \le K_i \le L)$
출력
첫 번째 줄에 가장 많은 김밥을 가져갈 것으로 예상하는 방청객의 고유 번호를 출력한다. 두 번째 줄에 가장 많은 김밥을 실제로 가져간 방청객의 번호를 고유 출력한다. 두 경우 모두, 만약 답이 되는 방청객의 고유 번호가 여러 개라면, 그 중 가장 작은 고유 번호를 출력한다.
힌트
#### 채점 첫째 줄이 정답인 경우, 60%의 점수를 얻는다. 둘째 줄이 정답인 경우, 40%의 점수를 얻는다. #### 예제 입력 1 ``` 10 3 2 4 7 8 6 9 ``` #### 예제 출력 1 ``` 3 1 ``` #### 예제 입력 2 ``` 10 3 1 3 5 7 8 9 ``` #### 예제 출력 2 ``` 1 1 ``` #### 예제 입력 3 ``` 10 5 1 1 1 2 1 3 1 4 7 8 ``` #### 예제 출력 3 ``` 4 5 ```