Sam has been teaching Jon the Game of Stones to sharpen his mind and help him devise a strategy to fight the white walkers. The rules of this game are quite simple:  The game starts with n piles of stones indexed from 1 to n. The i-th pile contains s_{i} stones. The players make their moves alternatively. A move is considered as removal of some number of stones from a pile. Removal of 0 stones does not count as a move. The player who is unable to make a move loses.

Now Jon believes that he is ready for battle, but Sam does not think so. To prove his argument, Sam suggested that they play a modified version of the game.

In this modified version, no move can be made more than once on a pile. For example, if 4 stones are removed from a pile, 4 stones cannot be removed from that pile again.

Sam sets up the game and makes the first move. Jon believes that Sam is just trying to prevent him from going to battle. Jon wants to know if he can win if both play optimally.


-----Input-----

First line consists of a single integer n (1 ≤ n ≤ 10^6) — the number of piles.

Each of next n lines contains an integer s_{i} (1 ≤ s_{i} ≤ 60) — the number of stones in i-th pile.


-----Output-----

Print a single line containing "YES" (without quotes) if Jon wins, otherwise print "NO" (without quotes)


-----Examples-----
Input
1
5

Output
NO
Input
2
1
2

Output
YES


-----Note-----

In the first case, Sam removes all the stones and Jon loses.

In second case, the following moves are possible by Sam: $\{1,2 \} \rightarrow \{0,2 \}, \{1,2 \} \rightarrow \{1,0 \}, \{1,2 \} \rightarrow \{1,1 \}$ 

In each of these cases, last move can be made by Jon to win the game as follows: $\{0,2 \} \rightarrow \{0,0 \}, \{1,0 \} \rightarrow \{0,0 \}, \{1,1 \} \rightarrow \{0,1 \}$

Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Game theory
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
memo = {}

def get_reachable_states(k, max_allowed):
	states = []
	for i in range(1, min(k, max_allowed) + 1):
		new_k = k - i
		states.append((new_k, i - 1))
	return states

def Grundy(k, max_allowed):
	if k == 0:
		return 0
	if (k, max_allowed) in memo:
		return memo[k, max_allowed]
	reachable_states = get_reachable_states(k, max_allowed)
	if len(reachable_states) == 0:
		memo[k, max_allowed] = 0
		return 0
	s = set()
	for state in reachable_states:
		s.add(Grundy(*state))
	i = 0
	while i in s:
		i += 1
	memo[k, max_allowed] = i
	return memo[k, max_allowed]
n = int(input())
GrundyTotal = 0
for i in range(n):
	k = int(input())
	GrundyTotal ^= Grundy(k, k)
print('YES' if GrundyTotal == 0 else 'NO')


ans = 0
for _ in range(int(input())):
	ans ^= int((8 * int(input()) + 1) ** 0.5 - 1) // 2
print(['YES', 'NO'][ans > 0])


from math import sqrt
k = 0
for t in range(int(input())):
	k ^= int(int(sqrt(8 * int(input()) + 1) - 1) / 2)
print('NO' if k != 0 else 'YES')


n = int(input())
arr = [int(input()) for i in range(n)]
b = [0 for i in range(n)]
s = 0
for i in range(n):
	j = int((arr[i] << 1) ** 0.5)
	if j * (j + 1) > arr[i] << 1:
		j -= 1
	s ^= j
if s != 0:
	print('NO')
else:
	print('YES')


import sys
input = sys.stdin.readline
dp = {}

def cal(x, y):
	(x, y) = (int(x), int(y))
	a = set()
	if (x, y) in dp:
		return dp[x, y]
	for i in range(min(int(60), x)):
		p = y & 1 << i
		if p > 0:
			continue
		r = cal(x - i - 1, y | 1 << i)
		a.add(r)
	cn = 0
	for i in range(len(a) + 2):
		if cn in a:
			cn += 1
		else:
			break
	dp[x, y] = cn
	return cn
n = int(input())
ans = 0
for i in range(n):
	x = int(input())
	ans ^= cal(x, 0)
if ans == 0:
	print('YES')
else:
	print('NO')


from math import ceil
from sys import stdin, stdout

def f(v):
	return ceil(((9 + 8 * v) ** 0.5 - 3) / 2)
(n, x) = (int(stdin.readline()), 0)
for i in range(n):
	x ^= f(int(stdin.readline()))
stdout.write('NO' if x else 'YES')


import sys
input = sys.stdin.readline

def large(x):
	for i in range(10, -1, -1):
		if i * (i + 1) // 2 <= x:
			return i
x = int(input())
l = []
for i in range(x):
	l.append(int(input()))
a = [large(i) for i in range(0, 61)]
lol = 0
for i in l:
	i = a[i]
	lol = lol ^ i
if lol == 0:
	print('YES')
else:
	print('NO')


s = 0
for t in range(int(input())):
	s ^= int((8 * int(input()) + 1) ** 0.5 - 1) // 2
print(['YES', 'NO'][s > 0])