Công ty Just Odd Inventions, Ltd. nổi tiếng với những phát minh kỳ lạ. Trong bài này, ta gọi công ty là JOI, Ltd.

Công ty vừa phát minh ra sản phẩm mới là những chiếc cà vạt chỉ có ưu điểm là dài. Có \(N+1\) loại cà vạt, được đánh số từ \(1\) đến \(N+1\). Chiếc cà vạt thứ \(i\) (\(1 \le i \le N+1\)) có độ dài \(A_i\).

Công ty tổ chức một buổi thử cà vạt với \(N\) nhân viên tham gia. Ban đầu, nhân viên thứ \(j\) (\(1 \le j \le N\)) đeo một chiếc cà vạt dài \(B_j\). Buổi thử diễn ra như sau:

1. Giám đốc chọn một chiếc cà vạt không được sử dụng trong buổi thử.
2. Mỗi nhân viên chọn một trong những chiếc cà vạt còn lại để thử. Không có hai nhân viên nào chọn cùng một chiếc.
3. Mỗi nhân viên tháo chiếc cà vạt đang đeo và đeo chiếc vừa chọn.

Nếu một nhân viên đang đeo cà vạt dài \(b\) thử chiếc cà vạt dài \(a\), mức độ lạ lẫm mà người đó cảm thấy là \(\max\{a-b,0\}\). Độ kỳ lạ của buổi thử được định nghĩa là mức độ lạ lẫm lớn nhất trong số các nhân viên.

Gọi \(C_k\) là độ kỳ lạ nhỏ nhất có thể của buổi thử khi giám đốc chọn loại bỏ chiếc cà vạt thứ \(k\). Hãy tính \(C_1,C_2,\ldots,C_{N+1}\) từ độ dài các cà vạt mới và các cà vạt mà nhân viên đeo ban đầu.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N
A_1 ... A_{N+1}
B_1 ... B_N

Dữ liệu ra

In ra một dòng chứa \(C_1,C_2,\ldots,C_{N+1}\) theo thứ tự, cách nhau bởi dấu cách.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với \(1 \le i \le N+1\).
• \(1 \le B_j \le 1\,000\,000\,000\) với \(1 \le j \le N\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(1\) điểm: \(N \le 10\)
2. \(8\) điểm: \(N \le 2000\)
3. \(91\) điểm: Không có

Ví dụ

3
4 3 7 6
2 6 4

2 2 1 1

5
4 7 9 10 11 12
3 5 7 9 11

4 4 3 2 2 2

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.