This page is still under construction.

Parts of this page are still being built. What you see may change.

Wowow

Time limit2sMemory limit512 MB

Summary
Maintain a dynamic set of (id, rating) friends under insertions, rating updates, and queries for the id holding the K-th highest rating.
Level

Medium7 of 10

Topics
Segment tree, Binary search, Sorting, Array
Solved
No attempts yet

Problem

In the world of World of Warcraft, there is a fiercely competitive ranking ladder. Players change their ratings over time, and new players — including more and more of your friends — keep joining the game.

You and your friends want to keep a simple database of everyone's scores. As the computer scientist of the group, you have been put in charge of maintaining it. Don't let your friends down!

Input

The first line contains an integer NN (1≤N≤1,000,0001 \le N \le 1{,}000{,}000): the number of operations. Each of the next NN lines is one of the following three commands.

  • N X R — a new friend joins the database. XX (1≤X≤1,000,0001 \le X \le 1{,}000{,}000) is the identifier of the new friend, and RR (1≤R≤1081 \le R \le 10^8) is that friend's rating.
  • M X R — modify an existing friend. XX is the identifier of a friend already in the database, and RR is that friend's new rating.
  • Q K — a query. KK is an integer with 1≤K≤1,000,0001 \le K \le 1{,}000{,}000, and it never exceeds the number of friends currently in the database.

Every rating value that appears anywhere in the input is distinct.

Output

For every Q K command, print one line with the identifier of the friend who has the KK-th highest rating in the database at that moment. K=1K = 1 refers to the top-rated friend, K=2K = 2 to the second-highest, and so on.

Examples7

  1. Example 1

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

  2. Example 2

    Input
    2
N 7 500
Q 1
    Expected output
    7

  3. Example 3

    Input
    6
N 1 300
N 2 100
N 3 200
Q 1
Q 2
Q 3
    Expected output
    1
3
2

  4. Example 4

    Input
    6
N 5 900
N 6 800
Q 1
M 5 100
Q 1
Q 2
    Expected output
    5
6
5

  5. Example 5

    Input
    5
N 100 50
N 200 60
N 300 40
Q 3
Q 1
    Expected output
    300
200

  6. Example 6

    Input
    9
N 1 10
N 2 20
N 3 30
Q 1
M 1 100
Q 1
M 2 200
Q 1
Q 2
    Expected output
    3
1
2
1

  7. Example 7

    Input
    6
N 111 100000000
N 222 1
N 333 50000000
Q 1
Q 2
Q 3
    Expected output
    111
333
222