John là một đại gia vùng Manchester. Một hôm John muốn dẫn bạn gái vào nhà hàng ăn. Nhà hàng có ~n~ bàn ăn, mỗi bàn ăn có hai loại giá ~a_i~ và ~b_i~, John phải trả ~a_i~ cho bàn ~i~ nếu đặt trước và ~b_i~ nếu không đặt trước. John chỉ đặt trước một bàn duy nhất, nhưng do sợ bạn gái mình ăn không đủ no nên John quyết định có gì sẽ đến đó sang ăn các bàn khác ăn nếu bạn gái mình vẫn đói. Vì John là một người rất cẩn thận nên anh muốn biết nếu mình và bạn gái nếu ăn ~k~ bàn thì sẽ tốn ít nhất bao nhiêu tiền.

Yêu cầu: Tính số tiền ít nhất John phải trả cho ~k~ bàn với ~k~ từ 1 đến ~n~.

Input

• Dòng đầu tiên chứa số ~n~ (~1 \le n \le 5 \times 10^5~)
• ~n~ dòng tiếp theo chứa ~a_i~ và ~b_i~ (~1 \le a_i, b_i \le 10^9~)

Output

• Ghi ra ~n~ dòng, dòng thứ ~i~ là số tiền ít nhất phải trả nếu John ăn ở ~i~ bàn.

Sample Input 1

3
10 5
9 3
10 5

Sample Output 1

9
13
18