Thống kê

Tháng \(6\) năm \(2022\), địa phương \(X\) tiến hành rà soát thống kê năm sinh của các công dân trong địa phương mình. Biết rằng địa phương \(X\) đã có đủ dữ liệu gồm họ tên và năm sinh của tất cả người dân đang sống.

Yêu cầu. Em hãy giúp địa phương \(X\) tìm:

• Số lượng năm của đoạn thời gian dài nhất không có người dân nào được sinh ra;
• Năm đầu và năm cuối của đoạn thời gian trên, nếu có nhiều đoạn thời gian dài nhất như thế thì đưa ra năm đầu và năm cuối của đoạn thời gian có năm sinh nhỏ nhất.

Việc tìm này chỉ thực hiện từ năm sinh nhỏ nhất đến năm sinh lớn nhất hiện có của người dân.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng công dân tại địa phương \((N \le 10^6)\);
• \(N\) dòng tiếp theo, mỗi dòng chứa họ tên và năm sinh của mỗi người dân. Giữa họ, tên lót, tên, năm sinh cách nhau bởi một dấu cách. Năm sinh có dạng \(4\) chữ số liền nhau.

Output

Ghi ra trên hai dòng:

• Dòng thứ nhất ghi số lượng năm của đoạn thời gian dài nhất không có người dân nào được sinh ra;
• Dòng thứ hai ghi năm đầu và năm cuối của đoạn thời gian tìm được, các năm cách nhau bởi một dấu cách.

Nếu không tìm được đoạn thời gian nào thỏa mãn thì ghi -1.

Input

%
4
Thai Ngoc Ha 1998
Tran Thi An 2002
Le Van Phu 1996
Tran Van Anh 2006

Output

%
3
1999 2001

Notes

Năm sinh nhỏ nhất là \(1996\), năm sinh lớn nhất là \(2006\).

Từ năm \(1996\) đến năm \(2006\) có hai đoạn thời gian cùng dài nhất có số lượng năm là \(3\) năm mà không có người dân nào được sinh ra là các năm \(1999\)–\(2001\) và \(2003\)–\(2005\).

Kết quả cần in là đoạn có năm bắt đầu nhỏ hơn, tức là \(1999\)–\(2001\).

Scoring

• (70%) \(0 < N \le 10^4\);
• (30%) \(10^4 < N \le 10^6\).