Đề bài

Có N ghế được đánh số từ 1 đến N. Ban đầu tất cả ghế đều trống.

Có Q nhóm khách đến tham dự.

Nhóm thứ i sử dụng toàn bộ các ghế từ L_i đến R_i.

Sau khi tất cả các nhóm đã đến, hãy xác định:

- Ghế được sử dụng nhiều lần nhất.
- Số lần sử dụng lớn nhất đó.

Nếu có nhiều ghế cùng đạt số lần sử dụng lớn nhất, in ra ghế có số hiệu nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q.

Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L, R.

Dữ liệu ra

In ra hai số:

seat max_count

Giới hạn

1 ≤ N ≤ 10⁶
1 ≤ Q ≤ 2×10⁵

Ví dụ

Input

10 3
1 5
3 8
4 6

Output

4 3

Giải thích

Ghế số 4 được cả 3 nhóm sử dụng.