Завдання № 25
відбірково-тренувальних зборів
команди міста Києва


за матеріалами ІІІ (міського) етапу 2009 року

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

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


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

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

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

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

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

Приклад

cclub.incclub.out
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
3
5
6
0







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

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


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

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

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

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

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

Приклади

factrl.infactrl.out
17 096
10007032

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