CF1369F.BareLee

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

首页