Gọi món ăn

Nam đang rất đói và muốn gọi món tại căn tin HCMUE. Căn tin có \(N\) món khác nhau.

Nam thật sự là một người ghiền ăn nên anh ấy muốn thử rất nhiều món khác nhau. Nhưng điểm đặc biệt của căn tin này là ở giá và thứ tự gọi món ăn.

Mỗi món \(i\) có hai mức giá:

• Nếu món \(i\) là món đầu tiên được gọi trong bữa ăn, Nam phải trả \(A_i\).
• Nếu món \(i\) không phải món đầu tiên, Nam chỉ phải trả \(B_i\).

Nam muốn ăn thật nhiều nhưng ví của anh ấy cũng có giới hạn của nó cho nên
Nam muốn biết nếu chọn đúng \(k\) món (\(1 \le k \le N\)), thì số tiền ít nhất phải trả là bao nhiêu.

Input

• Dòng đầu chứa số nguyên \(N\) (\(2 \le N \le 5 \cdot 10^5\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i\) và \(B_i\) (\(1 \le A_i, B_i \le 10^9\)).

Output

In ra \(N\) dòng, dòng thứ \(k\) là số tiền ít nhất cần thiết nếu Nam chọn đúng \(k\) món.

Scoring

• 30% số test có \(N \le 1000\).
• 30% số test tiếp theo có tất cả \(A_i = B_i\).
• 40% số test còn lại không có ràng buộc thêm.

Input

3
14 5
9 3
10 5

Output

9
13
18