1940. Walnut roll

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 aunique 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\ ≤\ L\ ≤\ 1000`), the length of the walnut roll.

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

Each of the following Nlines contains two positive integers `P_i` and `K_i` (`1\ ≤\ P_i\ ≤\ K_i\ ≤\ 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 numberof 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