1. Шаховий клуб

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам'ять: 32 МБ
Вхідний файл: cclub.in
Вихідний файл: cclub.out
Програма: cclub.*

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

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

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

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

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

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

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

Приклад

2. Факторіали

Максимальна оцінка: 100 балів
Обмеження на час: 0,5 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: factrl.in
Вихідний файл: factrl.out
Програма: factrl.*

Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

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

• при N = 7 кодом буде 504, бо 7! = 5040;
• при N = 17 кодом буде 096, бо 17! = 355687428096000.

Завдання
За даним натуральним числом N знайти три послідовні цифри числа N!, що записують безпосередньо перед нулями наприкінці запису числа N! .

Вхідні дані
Вхідний файл містить єдине ціле число N (7 ≤ N ≤1 000 000 000).

Вихідні дані
Вихідний файл має містити рівно три цифри — шуканий код.

Приклади

Примітка
У 20% вхідних файлів N не перевищує 10 000 000.
У 35% вхідних файлів N не перевищує 100 000 000.