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.


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

Difficulty: VERY_HARD
Tags: Dynamic programming

Graph traversal

Game theory
Skill types: Dynamic programming

Starter code:

Solutions:
def win(s, e):
	if e % 2:
		return s % 2 ^ 1
	if s > e // 2:
		return s % 2
	if s > e // 4:
		return 1
	return win(s, e // 4)

def lose(s, e):
	if s > e // 2:
		return 1
	return win(s, e // 2)

def game(n):
	res = [0, 1]
	for i in range(n):
		(s, e) = list(map(int, input().split()))
		(res[0], res[1]) = (res[win(s, e)], res[lose(s, e)])
	return res
n = int(input())
print(*game(n))


def f(s, e):
	if e % 2:
		return 1 - s % 2
	elif s * 2 > e:
		return s % 2
	else:
		return g(s, e // 2)

def g(s, e):
	if 2 * s > e:
		return 1
	else:
		return f(s, e // 2)
a = [tuple(map(int, input().split())) for i in range(int(input()))]
b = 1
for i in a:
	b1 = g(*i) | f(*i) << 1
	b = b1 ^ 3 if b == 2 else b1
	if b == 0:
		print('0 0')
		return
	elif b == 3:
		print('1 1')
		return
if b == 2:
	print('1 0')
else:
	print('0 1')


def win(s, e):
	if e == s:
		return False
	elif e == s + 1:
		return True
	elif e & 1:
		return s & 1 == 0
	elif e // 2 < s:
		return s & 1 == 1
	elif e // 4 < s:
		return True
	else:
		return win(s, e // 4)

def lose(s, e):
	return True if e // 2 < s else win(s, e // 2)

def main():
	res = [False, True]
	for _ in range(int(input())):
		(s, e) = [int(x) for x in input().split()]
		if res == [True, True]:
			continue
		if res == [False, False]:
			continue
		cur = [win(s, e), lose(s, e)]
		if res[0]:
			cur = [not x for x in cur]
		res = cur
	print(*[int(x) for x in res])
main()


import sys
inpy = [int(x) for x in sys.stdin.read().split()]

def win(s, e):
	if e == s:
		return False
	if e == s + 1:
		return True
	if e % 2 == 1:
		if s % 2 == 1:
			return False
		return True
	q = e // 4
	if s <= q:
		return win(s, q)
	q = e // 2
	if s > q:
		return (e - s) % 2 == 1
	return True

def lose(s, e):
	q = e // 2
	if s > q:
		return True
	else:
		return win(s, q)
t = inpy[0]
start = (True, False)
inpo = 1
v = (True, True)
for tc in range(t):
	if inpo + 1 >= len(inpy):
		print('wtf')
	(s, e) = (inpy[inpo], inpy[inpo + 1])
	inpo = inpo + 2
	v = (win(s, e), lose(s, e))
	if start[0] and start[1]:
		break
	if not start[0] and (not start[1]):
		break
	if start[1]:
		v = (not v[0], not v[1])
	start = (v[1], v[0])
if start[0] != True and start[0] != False or (start[1] != True and start[1] != False):
	print('wtf')
sw = 2
if start[1]:
	sw = sw - 1
	print(1, end=' ')
else:
	sw = sw - 1
	print(0, end=' ')
if start[0]:
	print(1)
	sw = sw - 1
else:
	print(0)
	sw = sw - 1
if sw:
	print(wtf)


import os
import sys
from io import BytesIO, IOBase
import threading
from heapq import heapify, heappush, heappop

def can_win(s, e):
	if e % 2 == 1:
		return 1 if s % 2 == 0 else 0
	else:
		if e // 2 < s <= e:
			return 1 if s % 2 == 1 else 0
		if e // 4 < s <= e // 2:
			return 1
		else:
			return can_win(s, e // 4)

def main():
	t = int(input())
	res = []
	for i in range(t):
		(si, ei) = map(int, input().split())
		res.append([can_win(si, ei), can_win(si, ei // 2) if ei >= 2 * si else 1])
	c = res
	f = 1
	s = 0
	for i in range(t):
		if f == 1 and s == 1:
			break
		if f == 0 and s == 0:
			break
		if s == 1:
			c[i][0] ^= 1
			c[i][1] ^= 1
		f = c[i][1]
		s = c[i][0]
	print(s, f)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()