Background

Special for beginners, ^_^

Description

A friend who works in a hospital asked BSNY to help build a registration system. The situation is this: recently more and more people come to the hospital, so many of them have to queue up, and only when a slot frees up is a batch of patients allowed in. But the hospital queue is different from an ordinary queue: in most cases, patients with more serious conditions should be seen first, so BSNY is asked to design the system so that the severity of the condition serves as the priority for deciding who is seen next.

Format

Input

The first line contains $n$, the number of operations.

For each operation, first read push or pop.

• In the push case, $a_i$ and $b_i$ follow, denoting the patient's name and the priority of the patient's condition respectively.

• After pop there is no further input, but you must produce output.

Output

For each pop operation, output the name and priority of the patient still in the queue who has the largest priority — that patient may now go in for treatment.

If there is nobody in the queue at that moment, output none. See the sample for details.

Samples

7
pop
push bob 3
push tom 5
push ella 1
pop
push zkw 4
pop

none
tom 5
zkw 4

Limitation

1s, 1024KiB for each test case.