时间限制：1秒　　内存限制：256M

---

题目描述

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

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

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

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

输入格式

输入的第一行包含一个正整数 \(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\)。

输出格式

输出两行。

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

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

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

输入输出样例 #1

输入 #1

10
3
2 4
7 8
6 9

输出 #1

3
1

输入输出样例 #2

输入 #2

10
3
1 3
5 7
8 9

输出 #2

1
1

输入输出样例 #3

输入 #3

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

输出 #3

4
5

说明/提示

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