Vrsta

Το αγαπημένο σχολικό μάθημα του Domagoj είναι το P.E. Κάθε P.E.. Το μάθημα ξεκινά με ασκήσεις προθέρμανσης. Ο δάσκαλος έχει έναν ενδιαφέροντα τρόπο να επιλέξει τον μαθητή που θα ηγηθεί της προθέρμανσης. Οι μαθητές στέκονται σε μια γραμμή ταξινομημένη με βάση το ύψος τους. Ο δάσκαλος θα επιλέξει τον μαθητή που στέκεται στη μέση της γραμμής. Αν δύο μαθητές είναι στη μέση, θα επιλέξει τον πιο κοντό. Για παράδειγμα: εάν οι μαθητές έχουν ύψη ~1\,3\,5\,7\,11~, ο μαθητής με ύψος ~5~ θα ηγηθεί των ασκήσεων προθέρμανσης.

Ο Domagoj δεν θυμάται πόσο ψηλοί είναι οι συμμαθητές του. Ευτυχώς, δίπλα του στέκεται ο Lavro που είναι πολύ καλός στην εκτίμηση των υψών των ανθρώπων. Δίνει ~n~ δηλώσεις στον Domagoj ως εξής: "Υπάρχουν μαθητές που μπαίνουν στο γυμναστήριο με ύψος ~v_i~". Μετά από κάθε δήλωση του Lovro, ο Domagoj ενδιαφέρεται για το ύψος του μαθητή που θα ηγηθεί της προθέρμανσης, αν έρθουν στo μάθημα P.E. μόνο οι μαθητές που μπήκαν στο γυμναστήριο. Βοηθήστε τον να απαντήσει στις ερωτήσεις του!

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~n~ ~(1 \le n \le 200\,000)~, τον αριθμό των δηλώσεων του Lovro.

Οι ακόλουθες ~n~ γραμμές περιέχουν δύο ακέραιους αριθμούς ~v_i~, ~a_i~ ~(1 \le v_i,\,a_i \le 10^9)~, το ύψος και τον αριθμό των μαθητών για κάθε δήλωση του Lovro.

Έξοδος

Στο ~i~-οστή από τις ~n~ γραμμές τυπώνετε την απάντηση στην ερώτηση του Domagoj μετά από ~i~ δηλώσεις του Lovro.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	19	~n, v_i \le 1\,000~
2	26	~a_1 = a_2 = \cdots = a_n = 1~
3	29	~v_1 < v_2 < \cdots < v_n~
4	36	Κανένας επιπλέον περιορισμός.

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

input

3
2 1
3 1
1 1

output

2
2
2

input

4
17 2
23 5
11 4
9 5

output

17
23
17
11

input

3
10 20
100 5
1000 5

output

10
10
10