### 2010 Canadian Computing Competition, Stage 2

## Day 1, Problem 3: Wowow

In the World of World of Warcraft, there is a very competitive ladder system. Sometimes players will change their rating. Also, new players (including more and more of your friends!) are constantly joining the game.

You and your group of friends would like to maintain a simple database with your scores, and you, as the computer scientist of the group, have been charged with the responsibility of maintaining it. Don't let your friends down!

### Input

The input will consist of an integer `N` (1 ≤ `N` ≤
10^{6}), followed by `N` lines. Each of these `N`
lines will correspond to one of the following three formats:

`N`

`X R`, where`N`

is the character`'N'`

to indicate a new friend has been added,`X`is a number (1 ≤`X`≤ 10^{6}) identifying this new friend, and`R`(1 ≤`R`≤ 10^{8}) is the rating of this new friend.`M`

`X R`, where`M`

is the character`'M'`

to indicate a modification of an existing friend,`X`is a number (1 ≤`X`≤ 10^{6}) identifying one of your friends, and`R`is the new rating assigned to this existing friend.`Q`

`K`, where`Q`

is the character`'Q'`

to represent a query,`K`is a number (1 ≤`K`≤ 10^{6}), and`K`is at most the number of your friends that have a rating at this point.

You may assume there will be no identical ratings in the input.

### Output

For each line of input of the format `Q`

`K`, you will
output a line containing the identifier of the `K`th highest rated
person in the database at that point. Note that when `K` = 1, that
is the top rated person, and `K` = 2 is the second best rated person,
and so on.

### Sample Input

7 N 10 1000 N 3 1014 Q 1 M 10 2000 Q 1 N 65 1950 Q 2

### Sample Output

3 10 65

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 3.00s

**Memory Limit:** 256M

**Added:** May 19, 2010

**Problem Types:**[Show]

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

jungernaut165on Apr 24, 2015 - 12:09:32 am UTC Hints?jeffreyxiaoon Apr 24, 2015 - 2:18:18 am UTC Re: Hints?jungernaut165on Apr 24, 2015 - 5:23:24 am UTC Re: Hints?awaykenedon Apr 24, 2015 - 5:01:23 pm UTC Re: Hints?jungernaut165on Apr 25, 2015 - 1:00:43 am UTC Re: Hints?fifimanon Apr 25, 2015 - 2:14:36 am UTC Re: Hints?awaykenedon Apr 25, 2015 - 11:44:28 pm UTC Re: Hints?jungernaut165on Apr 26, 2015 - 4:43:30 am UTC Re: Hints?awaykenedon Apr 26, 2015 - 1:43:51 pm UTC Re: Hints?jungernaut165on Apr 26, 2015 - 7:29:17 pm UTC Re: Hints?jargonon Apr 26, 2015 - 7:47:13 pm UTC Re: Hints?In any case, I wonder whether this is getting to be too much discussion about the answer... people looking for clarifications in the comments don't necessarily want to be given the solution.

jungernaut165on Apr 26, 2015 - 9:21:51 pm UTC Re: Hints?bobhob314on May 18, 2015 - 3:46:07 pm UTC Re: Hints?zzh8829on Sep 24, 2013 - 3:36:13 am UTC Wrong test data?Alexon Sep 24, 2013 - 5:54:44 am UTC Re: Wrong test data?bbi5291on May 19, 2010 - 11:48:16 pm UTC Huge input data