李习惯以时尚的方式完成他的故事,这次他勉强失败了,但白熊来了,帮助了他。 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$$$ 的整数,谁就输了。