← 返回题目列表

Codeforces · 1369/F

F. 裸李

中文机器翻译题面 查看原题

李习惯以时尚的方式完成他的故事,这次他勉强失败了,但白熊来了,帮助了他。 Lee对此非常感激,因此他决定向Ice Bear展示他的新游戏“Critic”......

本场比赛是一对一的比赛。它有$$$t$$$轮,每轮有两个整数$$$s_i$$$和$$$e_i$$$(在游戏开始前确定并已知,$$$s_i$$$和$$$e_i$$$每轮可能不同)。整数$$$s_i$$$ 被写在相应回合开始时的棋盘上。

玩家将轮流进行。每个玩家都会擦除棋盘上的数字(假设它是 $$$a$$$),并选择写 $$$2 \cdot a$$$ 或 $$$a + 1$$$ 来代替。谁写出的数字严格大于 $$$e_i$$$,谁就输掉这一轮,而另一个则赢得这一轮。

现在Lee想与Ice Bear玩“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$$$ 在游戏开始前每个人都知道。

输出

打印两个整数。

如果 Lee 可以独立于 Ice Bear 的动作而获胜,则第一个应该为 1,否则为 0。

如果李可以独立于白熊的动作而成为失败者,则第二个应该为 1,否则为 0。

示例

输入 #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

注意

请记住,无论谁写出大于 $$$e_i$$$ 的整数,谁就输了。