Popust

Ο Mirko είναι πεινασμένος σαν αρκούδα, ξέχνα το αυτό, είναι προγραμματιστής και έπεσε πάνω σε ένα τοπικό εστιατόριο. Το εστιατόριο προσφέρει ~N~ γεύματα και έχει μια ενδιαφέρουσα τιμολογιακή πολιτική: κάθε γεύμα ~i~ έχει δύο καθορισμένες τιμές, ~A_i~ και ~B_i~. Ο Mirko πληρώνει ~A~ μόνο για το πρώτο γεύμα που παρήγγειλε, ενώ οι τιμές ~B~ ισχύουν για όλα τα άλλα γεύματα.
Η Mikro δεν μπορεί να αποφασίσει πόσα γεύματα θα παραγγείλει. Για να διευκολύνει την απόφασή του, σας ζήτησε να υπολογίσετε, για κάθε ~k~ μεταξύ 1 και ~N~ (κλειστό διάστημα), την ελάχιστη συνολική τιμή για ~k~ παραγγελθέντα γεύματα. Ο Mirko δεν νοιάζεται ποια συγκεκριμένα γεύματα θα παραγγείλει ή με ποια σειρά θα τα παραγγείλει, ωστόσο δεν θα παραγγείλει το ίδιο γεύμα δύο φορές.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N\;(2 \le N \le 500\,000)~, τον αριθμό των διαφορετικών γευμάτων που προσφέρει το εστιατόριο.
Κάθε μία από τις ακόλουθες γραμμές ~N~ περιέχει δύο θετικούς ακέραιους, ~A_i~ και ~B_i\;(1 \le A_i, B_i \le 1\,000\,000\,000)~, τις τιμές για το γεύμα ~i~ όπως περιγράφονται παραπάνω.

Έξοδος

Η έξοδος πρέπει να αποτελείται από ~N~ γραμμές, όπου η γραμμή ~k~ περιέχει την ελάχιστη τιμή για την παραγγελία ακριβώς ~k~ διαφορετικών γευμάτων.

Παραδείγματα

input

3
10 5
9 3
10 5

output

9
13
18

Επεξήγηση του 1ου παραδείγματος:

~k = 1~: Ο Mirko πληρώνει ~A_2 = 9~ για το αρχικό γεύμα 2.
~k = 2~: Ο Mirko πληρώνει ~A_1 = 10~ για το αρχικό γεύμα 1, μετά ~B_2 = 3~ για το γεύμα 2.
~k = 3~: Ο Mirko πληρώνει ~A_1 = 10~ για το αρχικό γεύμα 1, μετά ~B_2 = 3~ για το γεύμα 2 και τέλος ~B_3 = 5~ για το γεύμα 3.

input

2
100 1
1 100

output

1
2

input

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

output

1000000000
2000000000
3000000000
4000000000
5000000000