Nikita 有一个堆栈。本问题中的栈是一种支持两种操作的数据结构。操作push(x)将一个整数x放入栈顶,操作pop()从栈顶删除整数i。 e.最后添加的。如果堆栈为空,则 pop() 操作不执行任何操作。
Nikita 对堆栈进行了 m 次操作,但忘记了它们。现在尼基塔想要记住他们。他一一记住它们,在第i步时,他记住了他所做的第一个操作。换句话说,他按照某种排列 p1,p2,...,pm 的顺序记住操作。在每一步之后,尼基塔都想知道在按照相应的顺序执行他已经记住的操作后,堆栈顶部的整数是什么。帮助他!
输入
第一行包含整数 m (1 ≤ m ≤ 105) — Nikita 进行的操作次数。
接下来的 m 行包含 Nikita 记得的操作。第 i 行以两个整数 pi 和 ti 开头(1 ≤ pi ≤ m,ti = 0 或 ti = 1)——他记住的第 i 步操作的索引以及操作的类型。如果操作是pop(),则ti 等于0;如果操作是push(x),则ti 等于1。如果操作是push(x),则该行还包含整数xi (1 ≤ xi ≤ 106)——添加到堆栈的整数。
保证从 1 到 m 的每个整数在整数 pi 中恰好出现一次。
输出
打印 m 个整数。执行完尼基塔记住的从 1 到 i 的所有操作后,整数 i 应等于堆栈顶部的数字。如果执行完所有这些操作后堆栈为空,则打印 -1。
示例
输入 #1
2 2 1 2 1 0
输出 #1
2 2
输入 #2
3 1 1 2 2 1 3 3 0
输出 #2
2 3 2
输入 #3
5 5 0 4 0 3 1 1 2 1 1 1 1 2
输出 #3
-1 -1 -1 -1 2
注意
在第一个例子中,Nikita 记住了第一步的操作后,push(2) 操作是唯一的操作,所以答案是 2。在他记住了 push(2) 之前完成的 pop() 操作后,答案保持不变。
在第二个示例中,操作是push(2)、push(3) 和pop()。尼基塔按照表演的顺序记住了它们。
在第三个示例中,Nikita 以相反的顺序记住了操作。