Mirko đang đói như một con gấu, gã lập trình viên và tình cờ gặp một nhà hàng địa phương. Nhà hàng phục vụ ~N~ bữa ăn và có chính sách giá thú vị: mỗi bữa ăn tôi có hai mức giá ấn định là ~A_i~ và ~B_i~. Mirko chỉ thanh toán cho ~A~ cho bữa ăn đặt đầu tiên, trong khi giá ~B~ áp dụng cho tất cả các bữa ăn khác.

Mikro không thể quyết định nên đặt bao nhiêu bữa ăn. Để đưa ra quyết định dễ dàng hơn, anh ấy đã yêu cầu bạn tính toán, với mỗi ~k~ trong khoảng ~1~ ~i~ ~N~ (đã bao gồm), tổng giá tối thiểu cho ~k~ bữa ăn được đặt. Mirko không quan tâm anh ấy gọi những bữa ăn cụ thể nào hay gọi chúng theo thứ tự nào, tuy nhiên anh ấy sẽ không gọi cùng một bữa ăn hai lần.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \le N \le 500 000)~, số lượng suất ăn khác nhau mà nhà hàng cung cấp.
• Mỗi ~N~ dòng tiếp theo chứa hai số nguyên dương ~A_i~ và ~B_i~ ~(1 ≤ Ai, Bi 1 000 000 000)~, giá bữa ăn ~i~ như đã mô tả ở trên.

Output

• Kết quả phải gồm ~N~ dòng, trong đó dòng ~k~ chứa giá tối thiểu để đặt đúng ~k~ suất ăn khác nhau.

Sample Input 1

3
10 5
9 3
10 5

Samle Output 1

9
13
18

Sample Input 2

2
100 1
1 100

Samle Output 2

1
2

Sample Input 3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Samle Output 3

1000000000
2000000000
3000000000
4000000000
5000000000

Chú ý:

Làm rõ ví dụ đầu tiên:

• ~k = 1~: Mirko trả ~A_2 = 9~ cho bữa ăn đầu tiên thứ ~2~.
• ~k = 2~: Mirko trả ~A_1 = 10~ cho bữa ăn ~1~, sau đó ~B_2 = 3~ cho bữa ăn ~2~.
• ~k = 3~: Mirko trả ~A_1 = 10~ cho bữa ăn ~1~, sau đó là ~B_2 = 3~ cho bữa ăn ~2~ và cuối cùng là ~B_3= 5~ cho bữa ăn ~3~.