Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. BareLee

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLee 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.

Input

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.

Output

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.

Examples

Input

3 5 8 1 4 3 10

Output

1 1

Input

4 1 2 2 3 3 4 4 5

Output

0 0

Input

1 1 1

Output

0 1

Input

2 1 9 4 5

Output

0 0

Input

2 1 2 2 8

Output

1 0

Input

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

Output

1 0

Note

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/28/2021 05:17:52 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|