Rakesh has built a model rocket and wants to test how stable it is. He usually uses a magic box which runs some tests on the rocket and tells if it is stable or not, but his friend broke it by trying to find out how stable he is (very delicate magic indeed). The box only gives a polynomial equation now which can help Rakesh find the stability (a failsafe by the manufacturers). 

Rakesh reads the manual for the magic box and understands that in order to determine stability, he needs to take every other term and put them in two rows. Eg. If the polynomial is:
10 x^4 + 12 x^3 + 4 x^2 + 5 x + 3, the first two rows will be: 

Row 1: 10       4       3

Row 2: 12       5       0

For all other rows, the nth element of the rth row is found recursively by multiplying the 1st element of the (r-1)th row and (n+1)th element of the (r-2)th row and subtracting it with 1st element of the (r-2)th row multiplied by (n+1)th element of the (r-1)th row.

So Row 3 will be (12 * 4 - 10 * 5)   (12 * 3 - 10 * 0)

Row 3: -2           36      0

Row 4: -442        0       0

Row 5: -15912    0       0

There will not be any row six (number of rows = maximum power of x + 1)

The rocket is stable if there are no sign changes in the first column. 

If all the elements of the rth row are 0, replace the nth element of the rth row by the nth element of the (r-1)th row multiplied by (maximum power of x + 4 - r - 2n).

If the first element of any row is 0 and some of the other elements are non zero, the rocket is unstable.

Can you help Rakesh check if his rocket is stable?

Input Format:

1. First row with number of test cases (T).

2. Next T rows with the coefficients of the polynomials for each case (10 12 4 5 3 for the case above).

Output Format:

1. "1" if stable (without "")

2. "0" if unstable (without "")

Sample Input: 

1

10 12 4 5 3

Sample Output:

0

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import random

def sign(i):
	if i > 0:
		return 1
	elif i <= 0:
		return 0
bleh = []
for _ in range(int(input())):
	p = list(map(int, input().rstrip().split()))
	max_rows = len(p)
	if all([x == 0 for x in p]):
		print(1)
		continue
	if max_rows <= 1:
		bleh.append(max_rows)
		continue
	max_pow = max_rows - 1
	if len(p) % 2 != 0 and len(p) > 0:
		p.append(0)
	max_col = len(p) // 2
	rows = [[0 for _ in range(max_col)] for _ in range(max_rows)]
	rows[0] = p[::2]
	rows[1] = p[1::2]
	if sign(rows[0][0]) != sign(rows[1][0]):
		print(0)
		continue
	for r in range(2, max_rows):
		for n in range(max_col - 1):
			rows[r][n] = rows[r - 1][0] * rows[r - 2][n + 1] - rows[r - 2][0] * rows[r - 1][n + 1]
	last = sign(rows[0][0])
	flag = 1
	for i in range(1, len(rows)):
		curr = sign(rows[i][0])
		if rows[r] == [0 for _ in range(max_col)]:
			for n in range(max_col):
				rows[r][n] = rows[r - 1][n] * (max_pow + 4 - (r + 1) - 2 * (n + 1))
		elif rows[i][0] == 0:
			if any([x != 0 for x in rows[i]]):
				flag = 0
				break
			else:
				curr = last
		if curr != last:
			flag = 0
			break
		last = curr
	print(flag)


def solve():
	c = list(map(int, input().strip().split()))
	n = len(c)
	if n <= 2:
		print(1)
		return
	k = (n + 1) // 2
	r = [[], []]
	for i in range(n):
		if i % 2 == 0:
			r[0].append(c[i])
		else:
			r[1].append(c[i])
	if len(r[1]) < k:
		r[1].append(0)
	r[0].append(0)
	r[1].append(0)
	while k > 0:
		p = []
		for i in range(1, k + 1):
			p.append(r[-1][0] * r[-2][i] - r[-1][i] * r[-2][0])
		r.append(p + [0])
		k -= 1
	r = [x[0] for x in r]
	(atleastz, allz) = (0, 1)
	for x in r:
		if x == 0:
			atleastz = 1
		else:
			allz = 0
	if atleastz:
		if allz:
			print(1)
		else:
			print(0)
		return
	for i in range(1, len(r)):
		if r[i] * r[i - 1] < 0:
			print(0)
			return
	print(1)

def main():
	t = int(input().strip())
	for _ in range(t):
		solve()

def __starting_point():
	main()
__starting_point()


def fun(st, en, l):
	for i in range(st, maxpow + 1):
		for j in range(0, m - 1):
			l[i][j] = l[i - 1][0] * l[i - 2][j + 1] - l[i - 2][0] * l[i - 1][j + 1]
for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = len(l)
	el = []
	ol = []
	for i in range(n):
		if i % 2 == 0:
			el.append(l[i])
		else:
			ol.append(l[i])
	if n % 2 != 0:
		ol.append(0)
	l = []
	l.append(el)
	l.append(ol)
	m = len(el)
	maxpow = n - 1
	for i in range(2, maxpow + 1):
		l.append([0] * m)
	fun(2, maxpow + 1, l)
	for i in range(maxpow + 1):
		cze = 0
		for j in range(m):
			if l[i][j] == 0:
				cze += 1
		if cze == m:
			for k in range(m):
				l[i][k] = l[i - 1][k] * maxpow + 4 - (i + 1) - 2 * (k + 1)
			fun(i + 1, maxpow + 1, l)
	check = 0
	for i in range(maxpow + 1):
		if l[i][0] == 0 and sum(l[i][1:]) != 0:
			print(0)
			check = 1
			break
	if check == 0:
		if l[0][0] > 0:
			signchange = 1
		else:
			signchange = -1
		c = 0
		for i in range(maxpow + 1):
			if l[i][0] > 0:
				temp = 1
			else:
				temp = -1
			if temp != signchange:
				print(0)
				c = 1
				break
		if c == 0:
			print(1)


def SR(coeff):
	size = len(coeff)
	max_power = size - 1
	Arr = []
	row1 = coeff[0::2]
	row2 = coeff[1::2]
	ln = len(row1)
	if size % 2 != 0:
		row2.append(0)
	row1.append(0)
	row2.append(0)
	Arr.append(row1)
	Arr.append(row2)
	sign = lambda x: 1 if x > 0 else -1
	s = [sign(row1[0]), sign(row2[0])]
	for r in range(2, size):
		Arr.append([0] * (ln + 1))
		for n in range(ln):
			Arr[r][n] = Arr[r - 1][0] * Arr[r - 2][n + 1] - Arr[r - 2][0] * Arr[r - 1][n + 1]
		s.append(sign(Arr[r][0]))
	for i in range(len(Arr)):
		if list(set(Arr[i])) == [0]:
			for n in range(len(Arr[i])):
				Arr[i][n] = Arr[i - 1][n] * (max_power + 4 - (i + 1) - 2 * (n + 1))
		elif Arr[i][0] == 0:
			return 0
	if len(set(s)) == 1:
		return 1
	else:
		return 0
T = int(input())
for t in range(T):
	coeff = [int(x) for x in input().split()]
	print(SR(coeff))


import numpy as np
t = int(input())
arr = []
for i in range(t):
	inp = input()
	arr.append(list(map(int, inp.split(' '))))

def gen_array(arr1, arr2, mp, rn):
	arrg = []
	if len(arr1) != len(arr2):
		arr1.append(0)
	for j in range(len(arr2) - 1):
		arrg.append(arr1[0] * arr2[j + 1] - arr2[0] * arr1[j + 1])
	ctz = not np.any(arrg)
	if ctz == True:
		for j in range(len(arrg)):
			arrg[j] = (mp + 4 - rn - 2 * (j + 1)) * arr1[j]
	return arrg

def check(rht):
	for i in range(len(rht) - 1):
		if rht[i][0] * rht[i + 1][0] <= 0:
			print(0)
			break
	else:
		print(1)
rh = []
for i in range(t):
	rh.append([])
	arr1 = []
	arr2 = []
	for j in range(len(arr[i]) - 1, -1, -1):
		if j % 2 == 0:
			arr1.append(arr[i][j])
		else:
			arr2.append(arr[i][j])
	arr1.reverse()
	arr2.reverse()
	rh[i].append(arr1)
	rh[i].append(arr2)
	for j in range(2, len(arr[i])):
		rh[i].append(gen_array(rh[i][j - 1], rh[i][j - 2], arr[i][0], j + 1))
	check(rh[i])


from math import copysign

def main():
	a = [int(c) for c in input().split()]
	assert 0 not in a
	k = len(a)
	prv = []
	cur = []
	for (i, e) in enumerate(a):
		if i % 2:
			cur.append(a[i])
		else:
			prv.append(a[i])
	n = len(prv)
	if len(cur) < n:
		cur.append(0)
	if copysign(1, prv[0]) != copysign(1, cur[0]):
		return 0
	for r in range(k - 2):
		nxt = [cur[0] * prv[i] - prv[0] * cur[i] for i in range(1, n)] + [0]
		if nxt == [0] * n:
			for i in range(n):
				nxt[i] = cur[i] * (k - r - 2 * i)
		(prv, cur) = (cur, nxt)
		if copysign(1, prv[0]) != copysign(1, cur[0]) or cur[0] == 0:
			return 0
	return 1
for _ in range(int(input())):
	print(main())


t = int(input())
for _ in range(t):
	coef = list(map(int, input().split()))
	mpow = len(coef) - 1
	row1 = []
	row2 = []
	mat = []
	for i in range(len(coef)):
		if i % 2 == 0:
			row1.append(coef[i])
		else:
			row2.append(coef[i])
	if len(coef) % 2:
		row2.append(0)
	mat.append(row1)
	mat.append(row2)
	idle = [0] * len(row1)
	for i in range(2, len(coef)):
		rown = []
		for j in range(1, len(row1)):
			val = mat[i - 1][0] * mat[i - 2][j] - mat[i - 2][0] * mat[i - 1][j]
			rown.append(val)
		for _ in range(len(rown), len(row1)):
			rown.append(0)
		mat.append(rown)
		if rown == idle:
			for i in range(len(mat)):
				if mat[i] == idle:
					for j in range(len(mat[i])):
						mat[i][j] = mat[i - 1][j] * (mpow + 4 - (i + 1) - 2 * (j + 1))
	s = 0
	sa = 0
	for i in mat:
		s += i[0]
		sa += abs(i[0])
	c = 0
	if s == sa:
		c = 1
		for i in range(len(mat)):
			if mat[i][0] == 0:
				c = 0
				break
	print(c)