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á ai và bi, John phải trả ai cho bàn i nếu đặt trước và bi 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.

Dữ liệu:

• Dòng đầu tiên chứa số n (1 ≤ n ≤ 5.10^5)

• n dòng tiếp theo chứa ai và bi (1 ≤ ai, bi ≤ 10^9)

Kết quả:

gồm 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

3
10 5
9 3
10 5

Sample Output

9
13
18