Priority Queue

A priority queue is a data structure which maintains a set $S$ of elements, each of with an associated value (key), and supports the following operations:

• $insert(S, k)$: insert an element $k$ into the set $S$
• $extractMax(S)$: remove and return the element of $S$ with the largest key

Write a program which performs the $insert(S, k)$ and $extractMax(S)$ operations to a priority queue $S$. The priority queue manages a set of integers, which are also keys for the priority.

Constraints

• The number of operations $\leq 2,000,000$
• $0 \leq k \leq 2,000,000,000$

Input

Multiple operations to the priority queue $S$ are given. Each operation is given by "insert $k$", "extract" or "end" in a line. Here, $k$ represents an integer element to be inserted to the priority queue.

The input ends with "end" operation.

Output

For each "extract" operation, print the element extracted from the priority queue $S$ in a line.

Example

Input

insert 8 insert 2 extract insert 10 extract insert 11 extract extract end

Output

8 10 11 2

inputFormat

Input

Multiple operations to the priority queue $S$ are given. Each operation is given by "insert $k$", "extract" or "end" in a line. Here, $k$ represents an integer element to be inserted to the priority queue.

The input ends with "end" operation.

outputFormat

Output

For each "extract" operation, print the element extracted from the priority queue $S$ in a line.

Example

Input

insert 8 insert 2 extract insert 10 extract insert 11 extract extract end

Output

8 10 11 2

样例

insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end

8
10
11
2

</p>