Chess Club
Petryk is a regular at the chess club, where many players gather. Each player is defined by two attributes: age and skill level. Players aim to enhance their skills by playing with the white pieces against opponents who are both older and more skilled. If multiple suitable opponents exist, they prefer the one with the lowest skill level. If there's still a tie, they choose the youngest.
Your task is to write a program that processes a sequence of events: either a player arriving at the club (referred to as a first-type event) or a player wanting to play a game with the white pieces (referred to as a second-type event). For each player wishing to play, determine their preferred opponent at that moment.
Input
The first line of the input contains a single natural number N — the number of events, where N ≤ 200000.
The following N lines describe the events in chronological order:
A line "P x y" indicates a player has arrived, aged x seconds with a skill level of y. Both parameters are natural numbers and less than 2^32. It is guaranteed that no two players have the same age and skill level simultaneously.
A line "G p" indicates that player p wants to play a game with the white pieces (players are numbered by their arrival order). It is guaranteed that all such events are valid, meaning the player number does not exceed the number of players who have arrived.
Output
For each second-type event (a player wanting to play with the white pieces), output the number of the player (in order of arrival) with whom the corresponding player would like to play, or 0 if no suitable player exists.