Ranking System

The ranking system needs to handle three types of requests:

• Upload: A player uploads a new score record. Their old record, if it exists, is overwritten.
• Query: Query the current ranking of a given player.
• Range Query: Return the ranking records within a specified rank interval. At most 10 records will be returned for such a query.

Ranking is determined in descending order of score. In case of a tie, the player with the lower ID gets the higher rank.

For example, if there are two players with score 300, and their IDs are 10 and 20, then player 10 is ranked higher.

The input begins with an integer T, the number of queries. Each query is one of the following formats:

• 1 x s: Update player x with a new score s. If the record for player x exists, it is replaced.
• 2 x: Query the current rank of player x. If the player does not exist, output -1.
• 3 l r: Query ranking records from rank l to rank r (inclusive). Only the first 10 records in this segment are returned. Each record should output the player's ID and score separated by a space on separate lines.

All changes are processed in order.

Note on Ranking: The ranking is 1-indexed, i.e. the top record is rank 1.

inputFormat

The first line contains an integer T (T ≥ 1), the number of queries.

Each of the following T lines contains a query in one of the three formats:

• For an update: 1 x s (x: player ID (integer), s: score (integer))
• For a rank query: 2 x (x: player ID)
• For a range query: 3 l r (l and r are integers specifying the rank interval, with 1-indexing)

outputFormat

For each query of type 2, output a single line with the player's current rank (or -1 if the player has no record).

For each query of type 3, output up to 10 lines. Each line contains the player's ID and score, separated by a single space, for players whose rank is within the given interval. The records must be in the order of the ranking.

sample

6
1 101 500
1 102 600
2 101
1 101 700
2 101
3 1 2

2
1
101 700
102 600

</p>