Mary just learned about a new, fashionable structure. It has "push" and "pop".

Implement a stack with two operations. The "first" operation push a number into stack, and "second" removes element from the top. For each "second" operation print the deleted number. It is guaranteed that all operations are correct.

Input

The first line contains the number of operations n (1 ≤ n ≤ 105). In the next n lines the first number is the operation number, the second number (only for the "first" operation) is a number to add, it is positive integer, not greater than 105.

Output

Print all removed numbers one by one, each on a separate line.