На училишниот натпревар годинава научивме дека медијана на дадена низа од непарен број на броеви е вредноста на елементот на средина на таа низа откако истата ќе биде сортирана. Ако низата има парен број броеви, тогаш за медијана се зема помалиот од двата елементи кои се во средина. На пример, ако низата е 2, 2, 5, 8, 9, 13, тогаш медијаната е 5.

Дијана решила да ви ја кажува низата дел по дел, со следната изјава: „Додај во низата k_i елементи со вредност v_i”.

После секое додавање, Дијана сака да и` кажете која е медијаната на низата во тој момент.

Влез

Во првиот ред е даден позитивен цел број N (1 ≤ N ≤ 200 000), бројот на изјави на Дијана.
Во следните N редови дадени се по два цели броја v_i, k_i (1 ≤ v_i, k_i ≤ 10⁹), вредноста на елементите и бројот на такви елементи кои се додаваат во низата.

Забелешка:
За 17 поени ќе важи: N, v_i ≤ 1000
За други 23 поени ќе важи: k₁ = k₂ = ... = k_N = 1
За други 24 поени ќе важи: v₁ < v₂ < ... < v_N

Излез

Во i-тиот ред отпечатете ја медијаната на низата после i изјави од Дијана.

Забелешка:
За побрзо извршување на вашата програма, овде ви препорачуваме да користите '\n' наместо ‘endl’ (на пример, cout << x << '\n';)

Ограничувања

Временско ограничување: 400 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
4 	
15 2
17 5
10 4
7 5

излез
15
17
15
10

влез
3
5 100	
12 10	
12 20

излез
5
5
5

Објаснување за првиот пример: После првото додавање, низата ќе изгледа вака: 15 15, медијаната на оваа низа е 15. После второто додавање, низата ќе изгледа вака: 15 15 17 17 17 17 17, па медијаната во овој случај е 17.