ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Summer 2010

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. НОД 2010

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Вам предложили работу в секретном проекте Агентства Федеральной Безопасности под кодовым названием «НОД 2010». Основным объектом исследования является набор целых положительных чисел. Вы должны понять, как будет изменяться наибольший общий делитель всех чисел этого набора при добавлении в него новых чисел или удалении лежащих там чисел. В начале эксперимента набор чисел пуст.

Исходные данные

В первой строке записано целое число q (1 ≤ q ≤ 105) — количество операций с набором. Каждая из следующих q строк имеет вид «+ x» или «- x». В первом случае число x добавляется в набор, а во втором случае — удаляется из него. Число x целое, положительное и не превосходит 109. Гарантируется, что из набора будут удаляться только числа, которые в нём лежат.

Результат

Выведите наибольший общий делитель всех чисел набора после каждой описанной операции. Согласно распоряжению 190р, наибольшим общим делителем пустого набора является единица.

Пример

исходные данныерезультат
5
+ 8
+ 6
+ 8
- 8
- 8
8
2
2
2
6
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2010
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1846. НОД 2010