题目描述

These days, the TV studio has started shooting another new season of Jamie Oliver's cooking show. This season, Jamie plans to introduce the delights of Croatian cuisine to the world. In the first episode, the master chef has baked a walnut roll $L$ meters long, the longest ever baked in this part of the world. After hours of sweating and toiling in the kitchen, he has decided to reward each one of his $N$ faithful spectators in the studio.

He has chopped the walnut roll into one meter long chops and marked them with numbers from $1$ do $L$, from left to right. Each spectator has received a unique number ID (a positive integer from $1$ to $N$), as well as a paper with two integers, $P$ and $K$. Each spectator was then allowed to take all chops from the $P$-th to the $K$-th, inclusive. Spectators were allowed to take their share in order of their ID numbers (spectator $1$ first, followed by spectator $2$, etc.). This order resulted in some spectators receiving fewer chops than they initially thought they would get. The following image corresponds to the first example test case:

Write a program to determine which spectator expected to get the most walnut roll chops, and which spectator actually got the most.

输入格式

The first line of input contains the positive integer $L$ ($1 \leq L \leq 1000$), the length of the walnut roll.

The second line of input contains the positive integer $N$ ($1 \leq N \leq 1000$), the number of spectators.

Each of the following $N$ lines contains two positive integers $P_i$ and $K_i$ ($1 \leq P_i \leq K_i \leq L$, $i = 1..N$), the values $P$ and $K$ as described in the problem statement for spectator number $i$.

输出格式

The first line of output must contain the ID number of the spectator who was expecting to receive the most walnut roll chops.

The second line of output must contain the ID number of the spectator who actually received the most walnut roll chops in the end.

In both cases, if there is more than one spectator satisfying the condition, output the one with the smallest ID.

10
3
2 4
7 8
6 9

3
1

10
3
1 3
5 7
8 9

1
1

10
5
1 1
1 2
1 3
1 4
7 8

4
5

提示

If the first number is correct, the solution is awarded 60% of points for that test case, and if the second number is correct, the solution is awarded 40% of points for that test case.