Roll Cake

A roll cake $L$ meters long is to be shared among $N$ audience members.

The cake is cut into $1$-meter pieces. The leftmost piece is numbered $1$ and the rightmost piece is numbered $L$. The audience members are numbered from $1$ to $N$.

Each audience member $i$ writes two integers $P_i$ and $K_i$ on a slip of paper, meaning they want pieces $P_i$ through $K_i$.

The host reads the slips in order, starting with member $1$. When reading member $i$'s slip, for each piece from $P_i$ to $K_i$ that has not yet been assigned to anyone, the host marks it with $i$'s number and gives it to that member. Any piece already marked with another member's number is skipped. As a result, a member may not receive all of the pieces they asked for.

The figure below illustrates how the pieces are handed out.

The number of pieces member $i$ expects to receive equals the number of pieces they wrote down, that is $K_i - P_i + 1$. Write a program that finds the number of the member who expected to receive the most pieces, and the number of the member who actually received the most pieces.

The first line contains the length of the roll cake $L$ ($1 \le L \le 1000$).

The second line contains the number of audience members $N$ ($1 \le N \le 1000$).

Each of the next $N$ lines contains the two integers $P_i$ and $K_i$ written by member $i$ ($1 \le P_i \le K_i \le L$).

On the first line, print the number of the member who expected to receive the most pieces.

On the second line, print the number of the member who actually received the most pieces.

In both cases, if more than one member satisfies the condition, print the smallest such member number.