C. Никита и стек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Никиты есть стек. Стек в данной задачи — структура данных, поддерживающая две операции. Операция push(x) кладет число x на верх стека, а операция pop() удаляет верхнее число из стека, то есть последнее добавленное. Если стек пустой, то операция pop() ничего не делает.

Никита сделал со стеком m операций, да забыл какие. Сейчас Никита пытается вспомнить, какие он сделал операции. Он вспоминает операции по одной. на i-м шаге он вспоминает, какой была операция, что была pi-й по очереди. Другими словами, он вспоминает операции в порядке некоторой перестановки p1, p2, ..., pm. После каждого шага Никита хочет знать, какое число лежало бы сверху стека после выполнения тех операций, что он вспомнил, в соответствующем порядке. Помогите ему!

Входные данные

В первой строке записано число m (1 ≤ m ≤ 105) — количество операций, которое сделал Никита.

В последующих m строках содержатся операции, которые вспоминает Никита. В строке i сначала записаны два числа pi и ti (1 ≤ pi ≤ m, ti = 0 или ti = 1) — номер по порядку, на котором была выполнена операция, которую Никита вспомнил на шаге i, и тип этой операции. ti равняется 0, если это операция pop(), и 1, если это операция push(x). При этом, если это операция push(x), то в этой же строке записано число xi (1 ≤ xi ≤ 106) — число, добавляемое в стек.

Гарантируется, что среди чисел pi каждое из чисел от 1 до m встретится ровно один раз.

Выходные данные

Выведите m чисел. Число i должно равняться числу на вершине стека после выполнения всех операций, которые Никита вспомнил на шагах от 1 до i. Если стек после выполнения этих операций пуст, то выведите -1.

Примеры
Входные данные
2
2 1 2
1 0
Выходные данные
2
2
Входные данные
3
1 1 2
2 1 3
3 0
Выходные данные
2
3
2
Входные данные
5
5 0
4 0
3 1 1
2 1 1
1 1 2
Выходные данные
-1
-1
-1
-1
2
Примечание

В первом примере, после того, как Никита вспомнил операцию на первом шаге, операция push(2) — единственная, и поэтому ответ равен 2. После того, как он вспомнил операцию pop(), которая была сделана до push(2), ответ не изменится.

Во втором примере операции следующие: push(2), push(3) и pop(). Никита вспоминает их в том порядке, в котором они были сделаны.

В третьем примере Никита вспоминает операции в обратном порядке.