Chủ tịch K muốn tạo ra một hoa văn trên bảng ô vuông gồm \(N\) hàng và \(N\) cột. Ô ở hàng thứ \(i\) từ trên xuống (\(1 \le i \le N\)) và cột thứ \(j\) từ trái sang (\(1 \le j \le N\)) được gọi là ô \((i,j)\). Mỗi ô sẽ được tô một màu, trong đó mỗi màu được biểu diễn bằng một số nguyên.

Hiện tại, các ô ở cột đầu tiên và hàng đầu tiên đã được tô màu. Cụ thể, ô \((i,1)\) (\(1 \le i \le N\)) có màu \(A_i\), còn ô \((1,j)\) (\(1 \le j \le N\)) có màu \(B_j\). Dữ liệu bảo đảm \(A_1=B_1\).

Chủ tịch K sẽ tô các ô còn lại theo thứ tự hàng \(i=2,3,\ldots,N\). Trong mỗi hàng \(i\), ông lần lượt xét các cột \(j=2,3,\ldots,N\) và tô ô \((i,j)\) bằng màu có số lớn hơn trong hai màu của ô \((i-1,j)\) và ô \((i,j-1)\). Nếu hai màu có cùng số thì tô ô \((i,j)\) bằng màu đó.

Sau khi cả \(N^2\) ô đã được tô, Chủ tịch K muốn biết màu nào xuất hiện trên nhiều ô nhất và số ô được tô màu đó. Cho kích thước bảng cùng thông tin màu của cột đầu tiên và hàng đầu tiên, hãy tìm hai giá trị này. Nếu có nhiều màu cùng xuất hiện trên nhiều ô nhất, hãy chọn màu có số lớn nhất trong số đó.

Dữ liệu vào

Dữ liệu vào có dạng:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Dữ liệu ra

In ra một dòng chứa hai số nguyên, cách nhau bởi một dấu cách: số của màu xuất hiện trên nhiều ô nhất và số ô được tô màu đó, theo đúng thứ tự này. Nếu có nhiều màu cùng xuất hiện trên nhiều ô nhất, hãy chọn màu có số lớn nhất.

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• \(1 \le B_j \le 10^9\) (\(1 \le j \le N\)).
• \(A_1=B_1\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. 15 điểm: \(N \le 500\), \(A_i \le 100\,000\) (\(1 \le i \le N\)), \(B_j \le 100\,000\) (\(1 \le j \le N\)).
2. 10 điểm: \(N \le 500\).
3. 20 điểm: \(A_i \le 2\) (\(1 \le i \le N\)), \(B_j \le 2\) (\(1 \le j \le N\)).
4. 25 điểm: \(A_i<A_{i+1}\) (\(1 \le i \le N-1\)), \(B_j<B_{j+1}\) (\(1 \le j \le N-1\)).
5. 30 điểm: Không có ràng buộc bổ sung.

Ví dụ

3
5 2 5
5 3 1

5 4

3
1 7 8
1 3 5

8 3

4
2 1 2 1
2 1 1 2

2 10

Nguồn

Đề bài Grid Coloring, JOI 2024/2025, vòng chung kết quốc gia, bài 1 (tiếng Nhật) của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.