Per có ~n~ tấm gỗ và muốn dùng chúng để dựng một hàng rào. Tấm gỗ thứ ~i~ có giá trị thẩm mỹ là ~A_i~ hoặc ~B_i~, tùy vào cách sử dụng.

Nếu Per chọn ~k~ tấm gỗ để dựng hàng rào quanh nhà, cô ấy sẽ dùng ~k - 1~ tấm để làm hàng rào và ~1~ tấm để làm cổng. Khi đó, các tấm dùng làm hàng rào có giá trị thẩm mỹ là ~A_i~, còn tấm dùng làm cổng có giá trị thẩm mỹ là ~B_i~. Tổng giá trị thẩm mỹ là tổng giá trị của ~k~ tấm gỗ được chọn.

Với mỗi giá trị ~k~ từ ~1~ đến ~n~, hãy giúp Per tính giá trị thẩm mỹ lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \ldots, A_n~.
• Dòng thứ ba chứa ~n~ số nguyên ~B_1, B_2, \ldots, B_n~.

Kết quả

In ra ~n~ số nguyên, mỗi số trên một dòng, trong đó số thứ ~i~ là giá trị thẩm mỹ lớn nhất khi Per dùng ~i~ tấm gỗ.

Ví dụ

Đầu vào:

2
1 2
2 1

Đầu ra:

2
4

Giải thích: Với ~k = 1~, tấm gỗ duy nhất chính là cổng, nên lựa chọn tốt nhất là tấm ~1~ với giá trị ~B_1 = 2~. Với ~k = 2~, cả hai tấm đều được dùng: lấy tấm ~1~ làm cổng và tấm ~2~ làm hàng rào cho ~B_1 + A_2 = 2 + 2 = 4~, tốt hơn cách còn lại ~B_2 + A_1 = 1 + 1 = 2~.

Giới hạn

• ~1 \le n \le 10^5~
• ~1 \le A_i, B_i \le 10^9~

Mỗi hàng rào luôn có đúng một cổng, nên với ~k = 1~ tấm gỗ duy nhất đó được tính là cổng và đóng góp ~B_i~. Kết quả có thể lên tới khoảng ~10^{14}~, nên không vừa trong số nguyên 32 bit.