Competitions

# 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 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