eolymp
Competitions

PP2: Week 9,10: May 17 - 30

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.

prb5087.gif

Time limit 2 seconds
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