Các môn thể thao phối hợp đòi hỏi vận động viên phải có sức mạnh và sự dẻo dai. Câu lạc bộ thể thao của nhà trường có ~n~ bạn tham gia, người thứ ~i~ (~1 \le i \le n~) có sức mạnh ~a_i~ và độ dẻo dai là ~b_i~.

Đội thi đấu có ~k~ người. Trong đội sẽ có một đội trưởng, những người còn lại là thành viên. Tiềm năng của đội được đánh giá bằng tổng sức mạnh của đội trưởng với độ dẻo dai của các thành viên.

Để chuẩn bị đấu giao hữu với trường bạn, huấn luyện viên quyết định sẽ đưa ra đội hình có tiềm năng thấp nhất, chủ yếu là tạo điều kiện cho mọi người có dịp cọ xát với thực tế, đồng thời cũng thử nghiệm các chiến thuật thi đấu.

Ví dụ, với ~n = 4~, sức mạnh và độ dẻo dai của mọi người tương ứng là ~A = (3, 7, 1, 6)~ và ~B = (6, 3, 8, 5)~. Nếu ~k = 3~ thì để có đội hình tiềm năng thấp nhất cần chọn các người ~2, 3, 4~ và chỉ định người ~3~ làm đội trưởng. Khi đó tiềm năng của đội sẽ là ~1 + 3 + 5 = 9~.

Do không biết trước lần này cần phải cử bao nhiêu người đi nên huấn luyện viên phải lên phương án cho mọi khả năng với ~k~ từ ~1~ đến ~n~.

Hãy đưa ra tiềm năng thấp nhất của đội được cử đi với ~k~ lần lượt nhận giá trị từ ~1~ đến ~n~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 2 \times 10^5~).
• Dòng thứ ~i~ trong ~n~ dòng sau chứa ~2~ số nguyên ~a_i~ và ~b_i~ (~1 \le a_i, b_i \le 10^9; 1 \le i \le n~).

Output

• Ghi ra ~n~ số nguyên - các tiềm năng thấp nhất tính được, mỗi số trên một dòng, số thứ ~i~ (~1 \le i \le n~) ứng với trường hợp hợp ~k = i~.

Sample Input 1

4
3 6
7 3
1 8
6 5

Sample Output 1

1
4
9
15

Subtasks