Christmas Gifts

Time limit2sMemory limit512 MB

Summary

Process visits in order: depots add gifts to Santa's collection, and each child takes the largest gift currently held.

Level: Medium4 of 10
Topics: Heap, Simulation, Greedy
Solved: No attempts yet

Problem

At Christmas, Santa hands out gifts to the children who behaved well. His sleigh is small and cannot carry every gift at once, so he stops at the depots he set up around the world and loads more gifts there. When he meets a good child, he hands over the single most valuable gift he is carrying at that moment.

You are given the depots and the children Santa visits, in order. For each child, print the value of the gift Santa hands over. If he is carrying no gift, print -1.

Input

The first line contains the number of visits $n$ . ( $1 \le n \le 5000$ )

Each of the next $n$ lines describes one visit, in order, and starts with an integer $a$ . If $a$ is 0, Santa meets a child. Otherwise Santa stops at a depot, and the values of the $a$ gifts loaded there follow on the same line, separated by spaces. ( $1 \le a \le 100$ )

Every gift value is a positive integer smaller than 100,000.

Output

For each line whose $a$ is 0, print the value of the gift handed to that child, one per line. Print -1 on that line if Santa has no gift to hand over. At least one line has $a$ equal to 0.

Examples2

Example 1
Input
```
5
0
2 3 2
0
0
0
```
Expected output
```
-1
3
2
-1
```
Example 2
Input
```
6
1 10
0
0
3 4 9 4
0
0
```
Expected output
```
10
-1
9
4
```