BareLee

题意翻译

### 题目描述 （以下内容并非逐字翻译，但并不影响做题） Lee 习惯于用一种新奇的方式结束他的故事，比如和 Ice Bear 玩一个叫做 Critic 的游戏。 游戏规则是这样的：这是一个 1V1 的游戏，有且仅有 $t$ 轮。对于每一轮，有且仅有两个双方均已知的，不会更改的整数 $s_i$ , $e_i$ 。其中 $s_i$ 被写在了黑板上。 现在，两名玩家同时上场，有两种操作，他/它只能并且必须选择一种操作： * 将黑板上的数 $a$ 改写为 $a+1$ * 将黑板上的数 $a$ 改写为 $2 \times a$ 最终，写上的 $a$ 大于这一轮的 $e_i$ 的人输掉该轮比赛。每一轮的失败者就是下一轮的起始者（首先上去写数的人）。整场比赛的输赢取决于最后一轮的输赢。 求出，如果 Lee 是第一轮比赛的起始者，他是否有必赢，必输策略。 ### 输入格式 第一行一个整数$t $，表示整场比赛有几轮。 下面$t $行，每行两个整数$s_i,e_i$,中间用空格隔开，第$i+1$行是第$i$ 场比赛的信息。 ### 输出格式 一行两个整数，中间用空格隔开，表示Lee是（1）否（0）有必赢，必输策略。

题目描述

Lee is used to finish his stories in a stylish way, this time he barely failed it, but Ice Bear came and helped him. Lee is so grateful for it, so he decided to show Ice Bear his new game called "Critic"... The game is a one versus one game. It has $ t $ rounds, each round has two integers $ s_i $ and $ e_i $ (which are determined and are known before the game begins, $ s_i $ and $ e_i $ may differ from round to round). The integer $ s_i $ is written on the board at the beginning of the corresponding round. The players will take turns. Each player will erase the number on the board (let's say it was $ a $ ) and will choose to write either $ 2 \cdot a $ or $ a + 1 $ instead. Whoever writes a number strictly greater than $ e_i $ loses that round and the other one wins that round. Now Lee wants to play "Critic" against Ice Bear, for each round he has chosen the round's $ s_i $ and $ e_i $ in advance. Lee will start the first round, the loser of each round will start the next round. The winner of the last round is the winner of the game, and the loser of the last round is the loser of the game. Determine if Lee can be the winner independent of Ice Bear's moves or not. Also, determine if Lee can be the loser independent of Ice Bear's moves or not.

输入输出格式

输入格式

The first line contains the integer $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of rounds the game has. Then $ t $ lines follow, each contains two integers $ s_i $ and $ e_i $ ( $ 1 \le s_i \le e_i \le 10^{18} $ ) — the $ i $ -th round's information. The rounds are played in the same order as given in input, $ s_i $ and $ e_i $ for all rounds are known to everyone before the game starts.

输出格式

Print two integers. The first one should be 1 if Lee can be the winner independent of Ice Bear's moves, and 0 otherwise. The second one should be 1 if Lee can be the loser independent of Ice Bear's moves, and 0 otherwise.

输入输出样例

输入样例 #1

3
5 8
1 4
3 10

输出样例 #1

1 1

输入样例 #2

4
1 2
2 3
3 4
4 5

输出样例 #2

0 0

输入样例 #3

1
1 1

输出样例 #3

0 1

输入样例 #4

2
1 9
4 5

输出样例 #4

0 0

输入样例 #5

2
1 2
2 8

输出样例 #5

1 0

输入样例 #6

6
216986951114298167 235031205335543871
148302405431848579 455670351549314242
506251128322958430 575521452907339082
1 768614336404564650
189336074809158272 622104412002885672
588320087414024192 662540324268197150

输出样例 #6

1 0

说明

Remember, whoever writes an integer greater than $ e_i $ loses.