Kỳ thi Duyên Hải đã trở thành một kỳ thi chất lượng và uy tín. Quy mô kỳ thi vượt qua ranh giới về mặt địa lý và đã thu hút nhiều tỉnh thành tham gia. Cùng với việc mở rộng về quy mô, kỳ thi cũng thay đổi hình thức thi. Kỳ thi Duyên Hải năm 2222, có ~n~ học sinh tham gia, các học sinh được đánh số từ 1 đến ~n~. Tất cả các học sinh sẽ phải trải qua ba bài thi ở ba môn Lập trình tính toán, Trí tuệ nhân tạo và An toàn thông tin với thể thức như sau:

• Với mỗi bài thi, khi các thí sinh thi xong, ban giám khảo sẽ tiến hành chấm điểm bằng nhiều tiêu chí nhằm đảm bảo rằng, không có hai thí sinh bằng điểm. Ban giám khảo lập bảng xếp hạng các thí sinh trên từng môn thi riêng biệt và gửi lên Ban tổ chức ba dãy số ~(p_1, p_2, ..., p_n), (a_1, a_2, ..., a_n), (s_1, s_2, ..., s_n)~ tương ứng là xếp hạng của ba môn Lập trình tính toán, Trí tuệ nhân tạo và An toàn thông tin. Các dãy số này đều là hoán vị của các số từ 1 đến ~n~, với ý nghĩa: học sinh thứ ~i~ xếp thứ ~p_i~ ở môn Lập trình tính toán, thứ ~a_i~ ở môn Trí tuệ nhân tạo và thứ ~s_i~ ở môn An toàn thông tin.
• Từ bảng xếp hạng của các môn, Ban tổ chức dùng phần mềm xếp hạng các thí sinh. Thí sinh thứ ~i~ có mức phân hạng là ~2^{p_i} + 2^{a_i} + 2^{s_i}~ và có thứ hạng chung cuộc được tính bằng số thí sinh có mức phân hạng nhỏ hơn cộng với 1. Theo cách xếp hạng của phần mềm, có thể có các thí sinh cùng thứ hạng.

Hiện tại, các thí sinh đã hoàn thành bài thi môn Lập trình tính toán và Trí tuệ nhân tạo, ban giám khảo đã chấm điểm và công bố bảng xếp hạng ở hai môn này. Tiếp theo, thí sinh chuẩn bị bước vào môn thi cuối cùng, môn An toàn thông tin. Để có được chiến lược thi phù hợp, mỗi thí sinh muốn biết thứ hạng chung cuộc tốt nhất và tồi nhất có thể của mình, sau khi môn thi cuối cùng diễn ra.

Yêu cầu: Cho biết thứ hạng của các thí sinh ở hai môn Lập trình tính toán và Trí tuệ nhân tạo, hãy giúp mỗi thí sinh tìm ra thứ hạng tốt nhất và tồi nhất chung cuộc có thể của mình khi xét trên mọi khả năng xảy ra đối với kết quả của môn An toàn thông tin.

Input

• Dòng đầu chứa số nguyên dương ~n~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~p_1, p_2, ..., p_n~ là một hoán vị của các số từ 1 đến ~n~, mô tả thứ hạng của các thí sinh ở môn Lập trình tính toán;
• Dòng thứ ba chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ là một hoán vị của các số từ 1 đến ~n~, mô tả thứ hạng của các thí sinh ở môn Trí tuệ nhân tạo.

Output

• Ghi ra ~n~ dòng, dòng thứ ~i~ (~1 \le i \le n~) gồm hai số nguyên dương ~b_i, w_i~ tương ứng là thứ hạng tốt nhất và tồi nhất chung cuộc có thể của thí sinh thứ ~i~.

Sample Input 1

3
1 2 3
2 1 3

Sample Output 1

1 2
1 2
3 3

Giải thích: Sau hai môn thi, tổng mức phân hạng của ba thí sinh tương ứng là 6, 6, 16. Dưới đây là 6 trường hợp có thể xảy ra: | Trường hợp | Thứ hạng môn An toàn thông tin | Tổng mức phân hạng của ba thí sinh | Thứ hạng chung cuộc | |---|---|---|---| | 1 | 1, 2, 3 | 8, 10, 24 | 1, 2, 3 | | 2 | 1, 3, 2 | 8, 14, 20 | 1, 2, 3 | | 3 | 2, 1, 3 | 10, 8, 24 | 2, 1, 3 | | 4 | 2, 3, 1 | 10, 14, 18 | 1, 2, 3 | | 5 | 3, 1, 2 | 14, 8, 20 | 2, 1, 3 | | 6 | 3, 2, 1 | 14, 10, 18 | 2, 1, 3 |

Như vậy, chỉ có hai khả năng xảy ra cho kết quả chung cuộc: Học sinh thứ ba chắc chắn xếp thứ ba, còn hai học sinh kia có thể đứng thứ nhất hoặc thứ hai.

Subtasks

• Có 30% số lượng test ứng với 30% số điểm thỏa mãn điều kiện: ~n \le 10~;
• Có 20% số lượng test khác ứng với 20% số điểm thỏa mãn điều kiện: ~n \le 50~;
• Có 20% số lượng test khác ứng với 20% số điểm thỏa mãn điều kiện: ~n \le 200~;
• Có 30% số lượng test còn lại ứng với 30% số điểm thỏa mãn điều kiện: ~n \le 2000~.