MINSTOCK - Minimum Stocks

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 ≤ 106)

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 ≤ 109) and (0 ≤ Z ≤ 109).

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".


Added by:Prakash Jha
Date:2018-09-19
Time limit:0.5s-1.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem

hide comments
2021-11-30 10:06:52
I got WA in test case 10 i removed the stock that are buyed now what should i do?
2020-09-20 22:43:23
Basic STL!
2019-07-16 11:06:04
Anyone getting WA. LOOK AT THIS.
Ignore the extra blank lines shown in the sample input and output - they’re an artifact of the HTML formatting and shouldn’t be there.

Remove the extra readlines and don’t output the blank line between test cases.

After several Wrong answers, a good soul helped me with this. Save WA save the world :p

Last edit: 2019-07-16 19:54:48
2019-01-07 22:46:56
Used same mapping .....got TLE in java and AC in cpp...........Nice question
2019-01-07 10:51:05
got WA on test case 10...any suggestions?

edit: if you buy a stock then you cant buy it again unless it is reintroduced to the market. good question.

Last edit: 2019-01-07 11:19:50
2018-12-10 21:37:37 Masha Zryanina
I did not understand why the output for XCD is 7 in the example, not 10. There were no instructions in the provided input that set price of XCD to 7.

Updated: my fault, did not read carefully.

Last edit: 2018-12-10 21:40:21
2018-09-24 19:38:56 DOT
Nice question. @Author, please mention the possible characters of the string X in the problem description.
RE : I have updated the input constrains, hope it's more clear now.

Last edit: 2018-09-25 06:36:40
2018-09-21 11:23:28 Palashvijay4O
My submission #22355284 is giving wrong answer on test case 9. My solution is in Java.

Reply : You have already got an AC. Cheers.

Last edit: 2018-09-21 19:05:52
2018-09-20 11:19:00
My code is giving correct result in 2 other IDEs and it's still showing runtime error here :(

REPLY : The constraints are 100000 not 10000. Check your code and also improve your time complexity.

Last edit: 2018-09-21 18:49:17
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.