最近，一家电视演播室开始拍摄杰米·奥利弗（Jamie Oliver）烹饪节目的新一季。

在这一季中，杰米计划向世界介绍克罗地亚美食的魅力。在第一集中，这位大厨烤制了一个长达 $L$ 米的核桃卷，这是该地区有史以来烤制的最长的核桃卷。在厨房里挥汗如雨地忙碌了几个小时后，他决定奖励演播室里的 $N$ 名忠实观众。

他将核桃卷切成了 $1$ 米长的切块，并从左到右用 $1$ 到 $L$ 的数字进行了标记。每位观众都获得了一个唯一的编号 ID（从 $1$ 到 $N$ 的正整数），以及一张写有两个整数 $P$ 和 $K$ 的纸条。然后，每位观众都可以拿走从第 $P$ 块到第 $K$ 块（包含边界）的所有切块。观众们被允许按照他们的 ID 顺序（观众 1 最先，接着是观众 2，依此类推）来拿走属于他们的部分。这种顺序导致一些观众实际得到的切块比他们最初想象的要少。

下图对应于第一个样例：

编写一个程序，确定哪位观众预计能获得最多的核桃卷切块，以及哪位观众实际获得的最多。

输入格式

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

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

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

输出格式

输出的第一行应包含预计获得最多核桃卷切块的观众 ID。

输出的第二行应包含最终实际获得最多核桃卷切块的观众 ID。

在这两种情况下，如果有多个观众满足条件，则输出其中 ID 最小的观众。

子任务

如果第一行数字正确，该测试点将获得 60% 的分数；如果第二行数字正确，该测试点将获得 40% 的分数。

样例

输入样例 1

10
3
2 4
7 8
6 9

输出样例 1

3
1

输入样例 2

10
3
1 3
5 7
8 9

输出样例 2

1
1

输入样例 3

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

输出样例 3

4
5