Шахматный клуб
Петрик регулярно посещает шахматный клуб. В клубе много шахматистов, и каждого из них характеризуют двумя числами: возрастом и уровнем игры. Каждый игрок стремится повысить свой уровень, поэтому хочет играть белыми фигурами только с партнером, который одновременно старше и сильнее его. Если таких кандидатов несколько, он выбирает того, у кого уровень игры наименьший. Если неопределенность сохраняется, он выбирает самого молодого.
Напишите программу, которая по последовательности событий: приход игрока в клуб (далее событие первого типа) или желание игрока сыграть партию белыми фигурами (далее событие второго типа), определит для каждого игрока, который хочет играть, с кем он бы хотел сыграть партию в данный момент.
Входные данные
Первая строка входного файла содержит одно натуральное число N — количество событий, N ≤ 200000.
Следующие N строк содержат описание событий в порядке их возникновения:
строка "P x y" означает, что пришел игрок возрастом x секунд и с уровнем игры y. Эти параметры игроков натуральные и меньше 2^32. Гарантировано, что ни одна пара игроков не может быть одновременно одного возраста и уровня игры;
строка "G p" означает, что игрок p хочет сыграть партию белыми фигурами (игроков нумеруют в порядке их прихода). Гарантировано, что все такие события корректны, то есть номер игрока не превышает количество игроков, которые пришли.
Выходные данные
Для каждого события второго типа (игрок хочет сыграть партию белыми фигурами) выведите номер игрока (в порядке прихода), с которым бы хотел сыграть соответствующий игрок, или 0, если такого нет.