e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Implement a stack

Implement a stack

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 (1n105). 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.

Time limit 2 second
Memory limit 128 MiB
Input example #1
6
1 1
1 2
2
1 4
2
2
Output example #1
2
4
1
Input example #2
3
1 1 
1 2
1 3
Output example #2