На экзамене по информатике Вася решал следующую задачу:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу $$$a$$$ каменей или увеличить количество камней в куче в два раза. Например, если $$$a = 2$$$, имея кучу из $$$10$$$ камней, за один ход можно получить кучу из $$$12$$$ или $$$20$$$ камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее $$$n$$$. Проигравшим считается игрок, сделавший последний ход, то есть получивший кучу, в которой будет $$$n$$$ или больше камней. В начальный момент в куче было $$$s$$$ камней. Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.»
К сожалению Вася не помнит значения $$$a$$$ и $$$n$$$, которые были на экзамене, но помнит при каких начальных $$$s$$$ выигрывали Петя или Ваня. Также он помнит что $$$a$$$, $$$n$$$ и $$$s$$$ не превосходили $$$10^3$$$. Напишите программу, которая по различным значениям $$$s$$$ и информации о выигрышах для этих $$$s$$$ найдет минимальные подходящие $$$a$$$ и $$$n$$$.
Первая строка входного файла содержит число $$$k$$$ — количество позиций $$$(1 \le k \le 1000)$$$, для которых Вася помнит исходы.
Далее следуют $$$k$$$ строк, каждая из которых содержит два целых числа. Первое из этих чисел — начальное количество камней $$$s_i$$$ $$$(0 \lt s_i \le 1000)$$$, второе равно $$$1$$$ если при количестве камней $$$s_i$$$ выигрывает Петя, или $$$2$$$ если при этом количестве камней выигрывает Ваня. Все начальные позиции $$$s_i$$$ различны.
Выходной файл должен содержать два целых числа $$$n$$$ и $$$a$$$, разделенных пробелом $$$(0 \lt n, a \le 1000)$$$.
Если задача допускает несколько решений то должно быть выведено решение с минимальным $$$n$$$, если для минимального $$$n$$$ существует несколько решений, то должно быть выведено решение с минимальными $$$n$$$ и $$$a$$$.
Если решения в заданных ограничениях не существует то должны быть выведены два нуля.
4
1 2
2 1
3 1
4 2
5 1
2
1 2
2 2
0 0
| Название |
|---|


