Kth Largest Element Queries

You are given an initially empty sequence and a series of operations. Each operation is either an insert x operation, which inserts the integer x into the sequence, or a kth k operation, which asks you to output the kth largest element in the sequence.

If the sequence after insertion is sorted in descending order as \(a_1 \geq a_2 \geq \dots \geq a_n\), then the kth largest element is \(a_k\). For example, with the operations insert 5, insert 2, and kth 1, the output would be 5 since 5 is the largest element.

The input is provided via standard input and the results for kth queries should be printed on standard output.

inputFormat

The input consists of multiple lines. Each line is an operation in one of the following formats:

1. insert x : Insert the integer x into the sequence.
2. kth k : Query the kth largest element in the current sequence.

The input terminates with a line containing only the word end.

outputFormat

For each kth query, output the kth largest element on a separate line.## sample

insert 5
insert 2
kth 1
insert 8
kth 2
insert 3
kth 3
end

5
5
3