Chọn cam

Một băng chuyền có \(N\) khay đựng cam được đánh số liên tiếp từ \(1\) đến \(N\). Mỗi khay chứa hai quả cam, mỗi quả cam được dán nhãn phân loại từ \(1\) đến \(5\). Trong đợt khuyến mãi này, người mua chỉ được chọn mua một loại cam bất kỳ trong một dãy liên tiếp các khay và mỗi khay người mua phải chọn một trong hai quả cam chứa trong khay đó.

Yêu cầu: Cho biết phân loại các quả cam trong \(N\) khay liên tiếp. Hãy viết một chương trình cho biết số lượng quả cam nhiều nhất một khách hàng có thể mua và loại cam tương ứng.

Input

Dữ liệu vào:

• Dòng đầu chứa một số nguyên \(N\).

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\) (\(1 \le A, B \le 5\)) cho biết phân loại của \(2\) quả cam trong lần lượt các khay.

Ràng buộc:

• \(40\%\) số điểm của bài: \(N \le 100\).

• \(80\%\) số điểm của bài: \(N \le 10\,000\).

• \(100\%\) số điểm của bài: \(N \le 100\,000\).

Output

In ra hai số nguyên lần lượt cho biết số lượng quả cam nhiều nhất một khách hàng có thể mua và loại cam tương ứng. Trong trường hợp có nhiều kết quả giống nhau hãy xuất ra kết quả ứng với loại cam nhỏ nhất.

Example 1

Input:

2
1 2
3 1

Output:

2 1

Example 2

Input:

3
1 2
2 3
4 3

Output:

2 2

Note

Ví dụ thứ nhất: cam loại \(1\) có ở cả hai khay nên mua được \(2\) quả loại \(1\). Các loại còn lại chỉ mua được tối đa \(1\) quả. Kết quả là \(2\) quả, loại \(1\).

Ví dụ thứ hai: cam loại \(2\) có ở khay \(1\) và \(2\), cam loại \(3\) có ở khay \(2\) và \(3\), mỗi loại mua được \(2\) quả. Hai loại bằng nhau nên chọn loại nhỏ hơn, kết quả là \(2\) quả, loại \(2\).