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

Лучше поздно, чем никогда

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

C. Алиса + Боб

Ограничение времени: 2.5 секунды
Ограничение памяти: 256 МБ
Легендарные персонажи математических задач Алиса и Боб столько раз вместе сыграли в различные игры, что между ними не могла не пробежать искорка симпатии, которую ветер времени вскоре раздул в огонь любви. И вот уже который год они живут вместе и продолжают искать новые оптимальные стратегии. Иногда в их жизни происходят довольно прозаичные события, и эта задача поведает вам об одном из них.
Однажды Боб, пересчитав деньги в семейном бюджете, обнаружил недостачу 1012 денежных единиц. Он подумал, что часть этой суммы могла потратить Алиса. Когда она пришла домой в новом платье и туфлях (что только усилило подозрения Боба), он спросил у неё, сколько денег она взяла из семейного бюджета. Алиса не сказала сумму прямо, но предложила Бобу сыграть в игру, в ходе которой он сможет узнать искомое число. Конечно же, Боб не смог устоять.
Вот правила этой игры. У Алисы есть целое число x (1 ≤ x ≤ 1012). Игра состоит из n ходов. На каждом ходу Боб спрашивает Алису, делится ли число x на некоторое целое положительное число di. Затем Алиса отвечает на вопрос Боба. После этого Боб должен назвать любое возможное целое число x'i (1 ≤ x'i ≤ 1012), которое удовлетворяет всей полученной информации (включая информацию, полученную на предыдущих ходах), либо сказать, что такого x'i не существует.
Боб сам выбрал, какие вопросы он будет задавать, но вот задача определения возможного числа x'i после каждого хода для него слишком сложна. Поможете Бобу вывести Алису на чистую воду?

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

В первой строке дано целое число n — количество ходов (1 ≤ n ≤ 105).
В следующих n строках дано описание ходов. Каждый ход описывается целыми числами di и ti (1 ≤ di ≤ 106; ti ∈ {0, 1}). В случае утвердительного ответа Алисы ti = 1, а в случае отрицательного ti = 0.

Результат

Выведите n строк, описывающих ответы Боба на каждом ходу. Каждая строка должна содержать либо число x'i (1 ≤ x'i ≤ 1012), либо -1, если подходящего x'i не существует.

Примеры

исходные данныерезультат
3
10 1
5 0
100500 0
100500
-1
-1
6
2 1
5 0
3 1
1 1
5 1
100500 0
12
12
12
12
-1
-1
6
1000000 1
999999 1
2 0
999998 1
999997 1
999996 1
999999000000
999999000000
-1
-1
-1
-1
Автор задачи: Кирилл Бороздин и Никита Сивухин, подготовка — Владимир Лесков
Источник задачи: Контест "Лучше поздно, чем никогда"
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2130. Алиса + Боб