Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. ПобедитеЛи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ли предпочитает завершать свои истории стильно, но не в этот раз. Благо, Белый Медведь успел придти к нему на помощь. В благодарность, Ли решил показать Белому его новую игру под названием «Critic»...

Данная игра — один на один. Она состоит из $$$t$$$ раундов, каждый раунд определяется двумя целыми числами $$$s_i$$$ и $$$e_i$$$ (которые определены заранее и известны перед началом игры, $$$s_i$$$ и $$$e_i$$$ могут отличаться от раунда к раунду). В начале соответствующего раунда число $$$s_i$$$ написано на доске.

Игроки ходят по очереди. Каждый игрок стирает число на доске (назовем его $$$a$$$) и выбирает, что написать: $$$2 \cdot a$$$ или $$$a + 1$$$. Тот, кто напишет на доске число строго больше чем $$$e_i$$$, проигрывает.

Сейчас Ли хочет сыграть в «Critic» против Белого, и для каждого раунда он уже выбрал соответствующие $$$s_i$$$ и $$$e_i$$$. Ли начинает первый раунд, и проигравший текущего раунда будет начинать в следующем раунде.

Победитель последнего раунда считается победителем всей игры, а проигравший, соответственно, проигравшим всей игры.

Определите, может ли Ли победить независимо от действий Белого. Также, определите, может ли он проиграть независимо от действий Белого.

Входные данные

В первой строке задано единственное целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество раундов в игре.

В следующих $$$t$$$ строках заданы по два целых числа $$$s_i$$$ и $$$e_i$$$ ($$$1 \le s_i \le e_i \le 10^{18}$$$) — информация про $$$i$$$-й раунд.

Раунды играются в том порядке, как они заданы во входных данных, $$$s_i$$$ и $$$e_i$$$ для всех раундов известны всем до начала игры.

Выходные данные

Выведите два числа.

Первым числом выведите 1, если Ли может победить независимо от действий Белого, иначе выведите 0.

Вторым числом выведите 1, если Ли может проиграть независимо от действий Белого, иначе выведите 0.

Примеры
Входные данные
3
5 8
1 4
3 10
Выходные данные
1 1
Входные данные
4
1 2
2 3
3 4
4 5
Выходные данные
0 0
Входные данные
1
1 1
Выходные данные
0 1
Входные данные
2
1 9
4 5
Выходные данные
0 0
Входные данные
2
1 2
2 8
Выходные данные
1 0
Входные данные
6
216986951114298167 235031205335543871
148302405431848579 455670351549314242
506251128322958430 575521452907339082
1 768614336404564650
189336074809158272 622104412002885672
588320087414024192 662540324268197150
Выходные данные
1 0
Примечание

Напоминаем, проигрывает тот, кто напишет число строго больше чем $$$e_i$$$.