문제
1 × L 격자의 각 칸에 과자가 하나씩 있다.
N명의 학생들은 각자 P번째에서부터 K번째 칸까지 위치한 과자를 가져갈 것이다.
각 학생이 가져갈 과자의 수는 정확히 K-P+1라고 예상할 수 있다.
하지만 실제로는 학생들이 과자를 순서대로 가져가기 때문에 마지막에 과자를 가져가는 사람이 불리하다. P와 K가 주어질 때, 가장 과자를 많이 가져갈 것으로 예측되는 학생의 번호와,
실제로 가장 과자를 많이 가져가는 학생의 번호를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에 L이 주어지고 두 번째 줄에 N이 주어진다. (1 ≤ L, N ≤ 1,000) 세 번째 줄부터 N개의 줄에는 각 학생의 P, K 값이 주어진다. (1 ≤ P ≤ K ≤ L) 먼저 입력된 학생이 과자를 먼저 가져간다.
출력
첫 번째 줄에는 가장 과자를 많이 가져갈 것으로 예측되는 학생의 번호를 출력하고, 두 번째 줄에는 실제로 가장 과자를 많이 가져가는 학생의 번호를 출력한다. 그런 학생이 여러 명이면 가장 작은 번호를 출력한다.
예제1
입력
10
3
2 4
7 8
6 9
출력
3
1
예제2
입력
10
3
1 3
5 7
8 9
출력
1
1
예제3
입력
10
5
1 1
1 2
1 3
1 4
7 8
출력
4
5
출처
COCI 2012/2013 contest4 1