Những ngày này, hãng phim truyền hình đã bắt đầu quay một mùa mới khác cho chương trình nấu ăn của Jamie Oliver. Mùa này, Jamie có kế hoạch giới thiệu những nét đẹp ẩm thực Croatia với thế giới. Trong tập đầu tiên, đầu bếp bậc thầy đã nướng một chiếc bánh óc chó dài ~L~ mét, chiếc bánh nướng dài nhất từng được nướng ở khu vực này trên thế giới. Sau nhiều giờ đổ mồ hôi và cực nhọc trong bếp, anh quyết định trao thưởng cho ~N~ khán giả trung thành của mình tại trường quay.

Anh ấy đã cắt cuộn quả óc chó thành những miếng dài một mét và đánh dấu chúng bằng các số từ ~1~ đến ~L~, từ trái sang phải. Mỗi khán giả đã nhận được một số ID duy nhất (một số nguyên dương từ ~1~ đến ~N~), cũng như một tờ giấy có hai số nguyên ~P~ và ~K~. Sau đó, mỗi khán giả được phép lấy tất cả các miếng từ thứ ~P~ đến thứ ~K~. Khán giả được phép chia phần theo thứ tự số ID của họ (khán giả 1 trước, tiếp theo là khán giả 2, v.v.). Lệnh này dẫn đến việc một số khán giả nhận được ít cú đánh hơn họ nghĩ ban đầu. Hình ảnh sau đây tương ứng với trường hợp thử nghiệm mẫu đầu tiên:

Viết chương trình để xác định xem khán giả nào mong đợi nhận được nhiều miếng bánh óc chó nhất và khán giả nào thực sự nhận được nhiều nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~L~ ~(1 ≤ L ≤ 1000)~, chiều dài của cuộn quả óc chó.
• Dòng đầu vào thứ hai chứa số nguyên dương ~N~ ~(1 ≤ N ≤ 1000)~, số lượng khán giả.
• Mỗi ~N~ dòng tiếp theo chứa hai số nguyên dương ~P_i~ và ~K_i~ ~(1 \le P_i \le K_i \le L, i = 1...N)~, các giá trị ~P~ và ~K~ như mô tả trong bài toán đối với số khán giả ~i~.

Output

• Dòng đầu tiên của đầu ra phải chứa số ID của khán giả đang mong đợi nhận được nhiều miếng bánh óc chó nhất.
• Dòng đầu ra thứ hai phải chứa số ID của khán giả thực sự nhận được nhiều miếng bánh óc chó nhất cuối cùng.
• Trong cả hai trường hợp, nếu có nhiều hơn một khán giả thỏa mãn điều kiện, hãy xuất ra khán giả có ID nhỏ nhất.

Scoring

• Nếu số thứ nhất đúng thì giải pháp được thưởng 60% số điểm cho trường hợp thử nghiệm đó và nếu số thứ hai đúng thì giải pháp được thưởng 40% số điểm cho trường hợp thử nghiệm đó.

Sample Input 1

10
3
2 4
7 8
6 9

Sample Output 1

3
1

Sample Input 2

10
3
1 3
5 7
8 9

Sample Output 2

1
1

Sample Input 3

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

Sample Output 3

4
5