eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Шаховий клуб

Шаховий клуб

Лимит времени 2 секунды
Лимит использования памяти 32 MiB

Петрик регулярно відвідує шаховий клуб. До клубу ходить багато шахістів, кожного з яких характеризують за допомогою двох чисел: віком та рівнем гри. Кожен з гравців прагне підвищити свій рівень гри, тому він хоче грати білими фігурами лише з одночасно досвіченішим і сильнішим партнером. Якщо таких кандидатів декілька, він вибирає того, чий рівень гри найменший. Якщо невизначеність зберіга­єть­ся, він вибирає наймолодшого.

Напишіть програму, яка за послідовністю подій: прихід гравця до клубу (надалі подія першого типу) або бажання кравця зіграти гру білими фігурами (надалі подія другого типу) встановить для кожного гравця, який бажає грати, з ким би він хоче зіграти партію у відповідний момент.

Входные данные

Перший рядок вхідного файлу містить єдине натуральне число N — кількість подій, N200000.

Наступні N рядків містять опис подій в порядку зростання часу:

  • рядок "P x y" означає, що прийшов гравець віком x секунд і з рівнем гри y. Ці параметри гравців натуральні й менші за 2^32. Гарантовано, що жодна пара гравців не може бути одночасно одного віку та сили гри;

  • рядок "G p" означає, що гравець p хоче зіграти гру білими фігурами (гравців нумерують у порядку їхнього приходу). Гарантовано, що всі такі події коректні, тобто номер гравця не перевищує кількість гравців, що прийшла.

Выходные данные

Для кожної події другого типу (гравець хоче зіграти гру білими фігурами) виведіть номер гравця (в порядку приходу), з яким би хотів зіграти відповідний гравець, або 0 у випадку якщо такого немає.

Пример

Входные данные #1
10
P 1 1
P 1 2
P 2 2
P 3 2
P 2 10
G 1
G 2
P 2 3
G 2
G 3
Выходные данные #1
3
5
6
0