Description

最近，电视台开始录制新一季的 Jamie Oliver 烹饪节目。本季中，Jamie 计划向全世界展示克罗地亚美食的魅力。在第一期节目中，这位大厨烘焙了一条长达 $L$ 米的核桃卷，这是该地区有史以来最长的核桃卷。经过长时间的辛勤烹饪，他决定奖励在场的 $N$ 位忠实观众。

他将核桃卷切成每段 $1$ 米的小段，并从左到右依次编号为 $1$ 到 $L$。每位观众都获得了一个唯一的编号 ID（从 $1$ 到 $N$ 的正整数），以及一张写有两个整数 $P$ 和 $K$ 的纸条。每位观众随后可以领取从第 $P$ 段到第 $K$ 段（包含两端）的所有核桃卷。观众按照 ID 编号的顺序依次领取（编号为 $1$ 的观众先领，然后是编号为 $2$ 的观众，依此类推）。由于领取顺序的影响，有些观众实际拿到的核桃卷段数比他们原本预计的要少。下表对应于第一个样例测试：

请编写程序，确定哪位观众期望获得最多的核桃卷段，以及哪位观众实际获得的核桃卷段最多。

Input Format

输入的第一行包含一个正整数 $L$（$1 \leq L \leq 1000$），表示核桃卷的长度。

第二行包含一个正整数 $N$（$1 \leq N \leq 1000$），表示观众人数。

接下来 $N$ 行，每行包含两个正整数 $P_i$ 和 $K_i$（$1 \leq P_i \leq K_i \leq L$，$i = 1..N$），分别表示第 $i$ 位观众纸条上的 $P$ 和 $K$。

Output Format

输出两行。

第一行输出期望获得核桃卷段数最多的观众编号。

第二行输出实际获得核桃卷段数最多的观众编号。

如有多名观众满足条件，输出编号最小的那一位。

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

Hint

如果第一行输出正确，则该测试点可获得 60% 分数；如果第二行输出正确，则该测试点可获得 40% 分数。

翻译由 ChatGPT-4.1 完成。