Himanshu wants to invest into stock market and his friend Navneet helps him by providing him instruction for next N days.

Navneet gives Himanshu 3 types of instruction,

1 X Y        There is a stock X available at price Y. Here X is a string and Y is an integer.

2 X Z        The price of stock X has changed to Z. Here X is a string and Z is an integer.

3 BUY      Buy the stock which has the lowest price.

You as a programmer, are given all the instructions of N days. Can you tell, which stock did Himanshu buy on which day. Print the output in same order as Himanshu bought the stock. See sample input and output for clarification.

At any point of time, there is atmost one stock of X. However, X can be made available to market again through another instruction of type 1.

All instructions are valid. i.e. There is always some stock to buy having the minimum price of all. Also if the price of X has changed, then X is already known and hasn't been bought yet.

Input

First line contains N. (1 ≤ N ≤ 10⁶)

Next N lines, each of them contains an instruction of any of 3 types. (Look at instruction format above.)

In any instruction, (X is a string of length upto 10 characters. All characters are from English alphabet, both small and capital), and (0 ≤ Y ≤ 10⁹) and (0 ≤ Z ≤ 10⁹).

Output

For each instruction of type 3, output two values X and Y. Where X is the name of Stock having minimum price and Y is the day on which it was bought.

Example

Input:
7
1 ABC 32
1 XDC 54
3 BUY
1 XCD 32
1 ABC 12
2 XDC 10
3 BUY
Output:
ABC 3
XDC 7

Explanation

On day 3, there is instruction to buy. There are two stocks available "XDC" and "ABC", since price of "ABC" is less, he buys it. After this "ABC" is not available in market anymore.

On day 7, there is instruction to buy. Of all stocks available, "XDC" has the least price and hence he buys "XDC".