One evening Johnny found some funny looking beens in his grandfather's garden shed, and decided to plant one of them. Next morning, to his surprise he found an enormous beanstalk growing in his back yard. Undaunted by its size, he decided to count its leaves.

You must know that beanstalks in Byteland grow in a very special way. At the lowest (1st) level, there is exactly one stem. At any level(including the 1st), a stem can end (forming exactly one leaf), or branch into exactly two stems which grow into the next level, following the same rules.

Johnny believes he has managed to count the number of leaves at each of the levels of the beanstalk. However, you must know that before he began to count, Johnny ate one or two of the other beans he found in his grandfather's shed, and that's why he is not quite sure of his results. Please verify whether Johnny's results may possibly be correct, at least in theory.

------ Input ------ 

The input starts with a line containing integer t, the number of test cases (1≤ t ≤ 20). The descriptions of exactly t test cases follow.
Each test case starts with an integer k, representing the number of levels of the beanstalk (1≤ k≤10^{6}). The next k non-negative space-separated integers (not greater than 10^{6}) represent the number of leaves of the beanstalk at successive levels, starting from level 1.

------ Output ------ 

For each test case, output a line containing exactly one of the words 'Yes' or 'No', depending on whether a beanstalk having the stated leaf counts can grow in accordance with the Bytelandian rules.

----- Sample Input 1 ------ 
2
3
0 1 2
3
0 0 3
----- Sample Output 1 ------ 
Yes
No

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms

Tree algorithms

Mathematics

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(len(l) - 1, 0, -1):
		if l[i] % 2 == 0:
			l[i - 1] += l[i] // 2
		else:
			print('No')
			break
	else:
		if l[0] == 1:
			print('Yes')
		else:
			print('No')


def branch_check(n, arr):
	cur_branches = 0.5
	for i in range(n):
		cur_branches = 2 * cur_branches
		if arr[i] > cur_branches:
			return 'No'
		cur_branches -= arr[i]
	return 'Yes' if cur_branches == 0 else 'No'
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(branch_check(n, arr))


def beanstalk(n, s):
	stem = 0.5
	for val in s:
		stem = 2 * stem - val
	if stem == 0:
		print('Yes')
	else:
		print('No')
t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	beanstalk(n, s)


def branching(N, A):
	stem = 0.5
	for a in A:
		stem = 2 * stem - a
		if stem < 0:
			break
	if stem == 0:
		return 'Yes'
	return 'No'

def solve():
	N = int(input())
	A = list(map(int, input().split(' ')))
	if N == 1:
		if A[0] == 1:
			print('Yes')
		else:
			print('No')
	else:
		print(branching(N, A))
for _ in range(int(input())):
	solve()


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	k = 1
	for i in range(n):
		if k < 0 or k > 10 ** 6 * (n - i):
			break
		k -= arr[i]
		k *= 2
	if k:
		print('No')
	else:
		print('Yes')
	t -= 1


t = int(input())
for i in range(t):
	k = int(input())
	leaf = map(int, input().split())
	stem = 0.5
	for l in leaf:
		stem = stem * 2 - l
	if stem == 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	input()
	levels = map(int, input().split())
	stem = 0.5
	for (i, val) in enumerate(levels):
		stem = 2 * stem - val
	if stem == 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	arr = map(int, input().split())
	prev = 0.5
	for i in arr:
		prev = 2 * prev - i
	print(('No', 'Yes')[prev == 0])


tn = int(input())
for _ in range(tn):
	k = int(input())
	arr = list(map(int, input().split()))
	if k == 1:
		if arr[0] == 1:
			print('Yes')
		else:
			print('No')
	else:
		sli = arr[-1] // 2
		for i in range(k - 2, 0, -1):
			sli = (sli + arr[i]) // 2
		if sli == 1:
			print('Yes')
		else:
			print('No')


def function(N, A):
	stem = 0.5
	for a in A:
		stem = 2 * stem - a
		if stem < 0:
			break
	if stem == 0:
		return 'Yes'
	return 'No'

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split(' ')))
		if N == 1:
			if A[0] == 1:
				print('Yes')
			else:
				print('No')
		else:
			val = function(N, A)
			print(val)
main()


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	s = 0
	c = 1
	for e in lis:
		s += e * c
		c = c / 2
	if s == 1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	nli = list(map(int, input().split()))
	stm = 0.5
	for a in nli:
		stm = stm * 2 - a
		if stm < 0:
			break
	if stm == 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	v = map(int, input().split())
	end = 0.5
	for i in v:
		end = end * 2 - i
	if end == 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	input()
	arr = map(int, input().split())
	leaf = 0.5
	for val in arr:
		leaf = 2 * leaf - val
	if leaf == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	k = int(input())
	arr = list(map(int, input().split()))
	flag = True
	if k == 1 and arr[0] == 1:
		print('Yes')
		continue
	stem = 0
	if arr[k - 1] % 2 == 0:
		stem = arr[k - 1] // 2
	else:
		print('No')
		continue
	for i in range(k - 2, 0, -1):
		if (stem + arr[i]) % 2 == 0:
			stem = (stem + arr[i]) // 2
		else:
			flag = False
			break
	if stem == 1 and flag and (arr[0] == 0):
		print('Yes')
	else:
		print('No')


t = int(input())
for tc in range(t):
	ignore = input()
	levels = map(int, input().split())
	stem = 0.5
	for (i, val) in enumerate(levels):
		stem = 2 * stem - val
	if stem == 0:
		print('Yes')
	else:
		print('No')


import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True

def bs(narr, arr, i, j, l):
	if i == j:
		narr[l] = arr[i]
		return arr[i]
	mid = (i + j) // 2
	lt = bs(narr, arr, i, mid, 2 * l)
	ri = bs(narr, arr, mid + 1, j, 2 * l + 1)
	narr[l] = lt + ri
	return lt + ri
arr = []
narr = [-1]
for l in rg(1, 2 * len(arr) + 1 + 1):
	narr.append(-1)

def pup(narr, i, j, p, val, l):
	narr[l] += val
	if i == j:
		return
	mid = (i + j) // 2
	if i <= p and p <= mid:
		lt = pup(narr, i, mid, p, val, 2 * l)
	else:
		ri = pup(narr, mid + 1, j, p, val, 2 * l + 1)

def rq(narr, i, j, L, R, l):
	print(i, j)
	if L <= i and j <= R:
		return narr[l]
	mid = (i + j) // 2
	ans = 0
	if L <= mid:
		ans += rq(narr, i, mid, L, R, 2 * l)
	if mid + 1 <= R:
		ans += rq(narr, mid + 1, j, L, R, 2 * l + 1)
	return ans

def istree(n, arr):
	next = 0.5
	for l in rg(n):
		next = 2 * next - arr[l]
	return next
for _ in rg(ii()):
	n = ii()
	arr = il()
	if istree(n, arr) == 0:
		ot('Yes')
	else:
		ot('No')


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		n = nl()
		nodes = ln()
		leafs = 0.5
		for i in nodes:
			leafs = leafs * 2 - i
		if not leafs:
			print('Yes')
		else:
			print('No')
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 1 / 2
	for i in l:
		c = 2 * c - i
	print('No') if c else print('Yes')


for i in range(int(input())):
	levels = int(input())
	leaves_by_levels = list(map(int, input().split()))
	stem_node = 0.5
	for _ in leaves_by_levels:
		stem_node = 2 * stem_node - _
	if stem_node == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	leaves = list(map(int, input().split()))
	if n == 1 and leaves[0] == 1:
		print('Yes')
		continue
	noOfLeaves = leaves[n - 1]
	stems = 0
	if noOfLeaves % 2 == 0:
		stems = noOfLeaves // 2
	else:
		print('No')
		continue
	found = True
	for index in range(n - 2, 0, -1):
		if (stems + leaves[index]) % 2 == 0:
			stems = (stems + leaves[index]) // 2
		else:
			found = False
			break
	if stems == 1 and found and (leaves[0] == 0):
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	k = int(input())
	l = list(map(int, input().split()))
	s = 0.5
	for j in l:
		s = 2 * s - j
	print('Yes' if s == 0 else 'No')


for i in range(int(input())):
	n = int(input())
	leaf = list(map(int, input().split()))
	f = 0
	stem = 0.5
	for _ in leaf:
		stem = 2 * stem - _
	if stem == 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	k = int(input())
	arr = list(map(int, input().split()))
	d = 0.5
	for i in arr:
		d = d * 2 - i
	print('Yes') if d == 0 else print('No')


for j in range(int(input())):
	k = int(input())
	x = list(map(int, input().split()))
	d = 0.5
	for i in x:
		d = d * 2 - i
	if d == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
level = []
x = [[] for i in range(t)]
for i in range(t):
	l = int(input())
	level.append(l)
	x[i] = list(map(int, input().split()))
for i in range(t):
	leaf = x[i]
	leaf.reverse()
	for (idx, j) in enumerate(leaf):
		if idx == level[i] - 1:
			if j == 1:
				print('Yes')
				break
			else:
				print('No')
		elif j % 2 == 0:
			leaf[idx + 1] += j / 2
		else:
			print('No')
			break


T = int(input())
for i in range(T):
	k = int(input())
	N = input().split(' ')
	x = 1 / 2
	for j in range(k):
		x = x * 2 - int(N[j])
	if x == 0:
		print('Yes')
	else:
		print('No')


T = int(input())
for t in range(T):
	K = int(input())
	N = input().split(' ')
	l = 1 / 2
	for i in range(K):
		l = l * 2 - int(N[i])
	if l == 0:
		print('Yes')
	else:
		print('No')


for xx in range(int(input())):
	n = int(input())
	arr = map(int, input().split())
	l = 0.5
	for i in arr:
		l = l * 2 - i
	if l == 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	l = 0.5
	for i in a:
		l = l * 2 - i
	if l == 0:
		print('Yes')
	else:
		print('No')


T = int(input())
for t in range(T):
	K = int(input())
	level = [int(x) for x in input().split()]
	stem = 0.5
	for x in level:
		stem = stem * 2 - x
	if stem == 0:
		print('Yes')
	else:
		print('No')