The country of BitLand is divided into N districts, and these districts are arranged in a circle: 1, 2, 3, ..., N, where i and i+1 are adjacent for all 1 ≤ i ≤ N-1, and also 1 and N are adjacent. It is given that N = o_{1} * o_{2}, where o_{1} and o_{2} are odd integers.

There are only 2 political parties in BitLand: the Zeros and the Ones. There was an election, in which each district chose it's representative who is either a Zero or a One. We know this data. i.e. for each of the N districts, we know whether their representative is a Zero or a One.

The N districts should be partitioned into o_{1} states, where each state consists of o_{2} consecutive districts.

For example, if o_{1} = 5 and o_{2}=3, then N=15, and {1,2,3} would be a valid state. {2,3,4}, {13,14,15}, {14,15,1}, {15,1,2} are other examples of valid states. But {3,5,6} is not a valid state, because the districts are not consecutive.

A state gets a One Governor if, among all the o_{2} district representatives belonging to it, there are more One district representatives than Zero representatives. And it gets a Governor who is from the Zero party, if the majority of its district representatives are from the Zero party. And because o_{2} is odd, there will be no ties.

The President of BitLand will be a One if the majority of the o_{1} state Governors are Ones. Otherwise, the President will be from the Zero party.

But the state boundaries have not been fixed yet. Given just the district-wise data (i.e. whether each district's representative is a Zero or a One), you need to find if there is a way to partition them into states such that the President is a One.

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

The first line contains one integer, T, which is the number of testcases.
The first line of each testcase contains two space separated integers, o_{1} and o_{2}, which are the number of states, and number of districts in each state, respectively.

The next line of each testcase contains N = o_{1} * o_{2} space separated integers: d_{1}, d_{2}, .., d_{N}. If d_{i} is 1, then it signifies that District i has chosen a One representative. If d_{i} is 0, then they have a Zero representative.

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

Each testcase should be in a new line, and should contain 1, if the President can be a One, and 0 otherwise.

------ Constraints ------ 

For all subtasks you may assume that: 
1 ≤ T ≤ 100$o_{1},o_{2} will be odd positive integers.$

$1 ≤ Summation of o_{1}*o_{2} over all testcases ≤ 10^{6}$
$0 ≤ d_{i} ≤ 1$

Subtask 1: For 10% of the score,

$1 ≤ Summation of o_{1}*o_{2} over all testcases ≤ 10^{4}$

Subtask 2: For further 20% of the score,
1 ≤ o_{1} ≤ 10^{4}
1 ≤ o_{2} ≤ 10^{2}

Subtask 3: For further 70% of the score,
No further constraints.$

----- Sample Input 1 ------ 
4
5 1
1 0 0 1 1
3 3
0 0 1 1 0 1 1 0 0
3 3
1 1 1 0 1 0 0 1 0
3 3
1 0 0 1 1 0 1 0 0
----- Sample Output 1 ------ 
1
1
1
0
----- explanation 1 ------ 

In the first testcase, each state should have only 1 district, and hence, there is no actual choice in constructing the states. There will be three One Governors, and two Zero Governors, and hence the President will be a One.

In the second testcase, each of the three states should should have 3 districts each. Consider the following partitioning of the districts into states: {2,3,4}, {5,6,7} and {8,9,1}. So, the first state consists of the districts {2,3,4}, and the representatives of these correspond to {0,1,1}. The majority is One, and hence the first state will have a One Governor. The representatives corresponding to the second state are {0,1,1}, and so again, this will have a One Governor. The third state has representatives {0,0,0}, and hence will have a Zero Governor. On the whole, there are two One Governors, and one Zero Governor, and hence the President will be a One. And since there is a way to partition the districts into states, in which the President is a One, the answer is 1.

In the third testcase, each of the three states should should have 3 districts each. Consider the following partitioning of the districts into states: {3,4,5}, {6,7,8} and {9,1,2}. So, the first state consists of the districts {3,4,5}, and the representatives of these correspond to {1,0,1}. The majority is One, and hence the first state will have a One Governor. The representatives corresponding to the second state are {0,0,1}, and since the majority is Zero, this will have a Zero Governor. The third state has representatives {0,1,1}, and as Ones are in majority, this will have a One Governor. On the whole, there are two One Governors, and one Zero Governor, and hence the President will be a One. And since there is a way to partition the districts into states, in which the President is a One, the answer is 1.

In the fourth testcase, you can check that no matter how you construct the states, the President cannot be a One. Hence, the answer is 0.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Constructive algorithms


Solutions:
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	d = list(map(int, input().split()))
	n = a * b
	f = 0
	p = 0
	ans = [0] * (n + b)
	for j in range(n + b):
		p += d[j % n]
		ans[j] = p
	for j in range(b):
		w = 0
		for k in range(a):
			s = j + b * k
			e = s + b
			v = ans[e - 1]
			if s - 1 >= 0:
				v -= ans[s - 1]
			if v > int(b / 2):
				w += 1
		if w > int(a / 2):
			f = 1
			break
	print(f)


t = int(input())
for _ in range(t):
	(noState, size) = map(int, input().split())
	d = list(map(int, input().split()))
	n = noState * size
	flag = 0
	tmp = 0
	ans = [0] * (n + size)
	for i in range(n + size):
		tmp += d[i % n]
		ans[i] = tmp
	for i in range(size):
		noWin = 0
		for j in range(noState):
			start = i + size * j
			end = start + size
			noVotes = ans[end - 1]
			if start - 1 >= 0:
				noVotes -= ans[start - 1]
			if noVotes > int(size / 2):
				noWin += 1
		if noWin > int(noState / 2):
			flag = 1
			break
	print(flag)


for _ in range(int(input())):
	(o1, o2) = map(int, input().split())
	l = list(map(int, input().split()))
	ll = []
	s = 0
	for i in range(o2):
		s += l[i]
	ll.append(s)
	i = 0
	for j in range(o2, o1 * o2):
		s = s - l[i] + l[j]
		ll.append(s)
		i += 1
	j = 0
	while i != o1 * o2 - 1:
		s = s - l[i] + l[j]
		ll.append(s)
		i += 1
		j += 1
	f = 0
	for i in range(o2):
		j = i
		c = 0
		while j < o1 * o2:
			if ll[j] > o2 - ll[j]:
				c += 1
			j += o2
		if c > o1 - c:
			f = 1
			break
	if f == 1:
		print('1')
	else:
		print('0')


n = int(input())
statedistricts = []
datapoints = []
datapointssum = []
for i in range(n):
	(nstates, ndistricts) = map(int, input().split())
	statedistricts.append((nstates, ndistricts))
	l = list(map(int, input().split()))
	s = []
	cs = 0
	for d in l:
		if d == 1:
			cs += 1
		s.append(cs)
	datapoints.append(l)
	datapointssum.append(s)
for i in range(n):
	(nstates, ndistricts) = statedistricts[i]
	districtcount = 0
	flag = False
	while districtcount < ndistricts:
		jump = districtcount
		onewon = 0
		statecount = 0
		prevonecount = 0 if districtcount == 0 else datapointssum[i][districtcount - 1]
		while statecount < nstates:
			if jump + ndistricts <= ndistricts * nstates:
				countofones = datapointssum[i][jump + ndistricts - 1] - prevonecount
			else:
				countofones = datapointssum[i][ndistricts * nstates - 1] - prevonecount + datapointssum[i][(jump + ndistricts) % (ndistricts * nstates) - 1]
			if countofones > ndistricts / 2:
				onewon += 1
			jump += ndistricts
			prevonecount = datapointssum[i][jump % (ndistricts * nstates) - 1]
			statecount += 1
		districtcount += 1
		if onewon > nstates / 2:
			flag = True
			break
	if flag:
		print(1)
	else:
		print(0)


import math
t = int(input())
for I in range(0, t):
	(o1, o2) = map(int, input().split())
	n = o1 * o2
	a = [int(i) for i in input().split()]
	cumm = [0 for i in range(0, n + 1)]
	cumm[1] = a[0]
	for i in range(2, n + 1):
		if a[i - 1] == 1:
			cumm[i] = cumm[i - 1] + 1
		else:
			cumm[i] = cumm[i - 1]
	m1 = math.floor(o1 / 2) + 1
	m2 = math.floor(o2 / 2) + 1
	flag = 0
	for i in range(0, o2):
		c = 0
		k = i
		for j in range(0, o1):
			if k + o2 < n and cumm[k + o2] - cumm[k] >= m2:
				c = c + 1
			elif k + o2 >= n and cumm[n] - cumm[k] + cumm[o2 - (n - k)] >= m2:
				c = c + 1
			k = k + o2
		if c >= m1:
			print('1')
			flag = 1
			break
	if flag == 0:
		print('0')


t = int(input())
while t:
	t -= 1
	(o1, o2) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 0
	dist = []
	for i in range(0, o1 * o2, o2):
		dist.append(a[i:i + o2].count(1))
	c = 0
	for i in dist:
		if i > o2 // 2:
			c += 1
	if c > o1 // 2:
		print(1)
	else:
		f = 1
		for i in range(1, o2):
			k = 0
			for j in range(i, o1 * o2, o2):
				dist[k] += a[(j + o2 - 1) % (o1 * o2)] - a[j - 1]
				k += 1
			c = 0
			for i in dist:
				if i > o2 // 2:
					c += 1
			if c > o1 // 2:
				print(1)
				f = 0
				break
		if f:
			print(0)


for _ in range(int(input())):
	[o1, o2] = [int(i) for i in input().split()]
	n = o1 * o2
	a = [int(i) for i in input().split()]
	l = sum(a[:o2])
	b = [l]
	for i in range(1, n):
		b.append(b[-1] + a[(i + o2 - 1) % n])
		b[-1] -= a[i - 1]
	for i in range(n):
		if b[i] > o2 // 2:
			b[i] = 1
		else:
			b[i] = 0
	for i in range(o2):
		j = i + o2
		while j < n:
			b[i] += b[j]
			j += o2
		if b[i] > o1 // 2:
			print('1')
			break
	else:
		print('0')


t = int(input())
while t > 0:
	flag = 0
	o = input().split()
	n = int(o[0])
	q = int(o[1])
	sum = [0] * q
	arr = input().split()
	i = yt = rem = 0
	if n == 1 or q == 1:
		yt = 1
		while i < n:
			rem = rem + int(arr[i])
			i = i + 1
			if rem > n / 2:
				flag = 1
				break
	while i < q - 1 and yt == 0:
		arr.append(arr[i])
		i = i + 1
	i = k = 0
	while arr and yt == 0:
		arr[i] = int(arr[i])
		if i < q:
			rem = rem + arr[i]
		else:
			if rem > q / 2:
				pos = i % q
				sum[pos] = sum[pos] + 1
				if sum[pos] > n / 2:
					flag = 1
					break
			rem = rem - arr[k]
			rem = rem + arr[i]
			k = k + 1
		i = i + 1
		if i == n * q + (q - 1):
			break
	if rem > q / 2 and yt == 0:
		sum[q - 1] = sum[q - 1] + 1
	if sum[q - 1] > n / 2 and yt == 0:
		flag = 1
	if flag == 1:
		print('1')
	else:
		print('0')
	t = t - 1


import sys

def ones_win(states, dps, num_states):
	return [int(ones > dps / 2) for ones in states].count(1) > num_states / 2

def main():
	for _ in range(int(sys.stdin.readline())):
		(num_states, dps) = list(map(int, sys.stdin.readline().split()))
		districts = list(map(int, sys.stdin.readline().split()))
		states = [sum(districts[i * dps:(i + 1) * dps]) for i in range(num_states)]
		found = 0
		for i in range(dps):
			for j in range(num_states):
				if i == 0:
					break
				s = j * dps + i - 1
				e = ((j + 1) * dps + i - 1) % (dps * num_states)
				if districts[s] != districts[e]:
					if districts[e] == 0:
						states[j] -= 1
					else:
						states[j] += 1
			if ones_win(states, dps, num_states):
				found = 1
				break
			if len(states) == 0:
				break
		print(found)
main()


t = int(input())
for i in range(t):
	(o1, o2) = list(map(int, input().strip().split()))
	d = list(map(int, input().strip().split()))
	o1by2 = o1 // 2
	o2by2 = o2 // 2
	flag = 0
	ll = [0] * o2
	s = sum(d[0:o2])
	if s > o2by2:
		ll[0] += 1
	for i in range(o1 * o2 - o2):
		s = s - d[i] + d[o2 + i]
		if s > o2by2:
			ll[(i + 1) % o2] += 1
	for (i, j) in zip(range(o2 - 1), range(o1 * o2 - o2, o1 * o2 - 1)):
		s = s - d[j] + d[i]
		if s > o2by2:
			ll[(i + 1) % o2] += 1
	count = 0
	for i in ll:
		if i > o1by2:
			flag = 1
			break
	print(flag)


for i in range(int(input())):
	(o1, o2) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	sum_array = []
	r = []
	for j in range(o1 * o2):
		r.append(a[j])
	for j in range(o2 - 1):
		r.append(a[j])
	count = 0
	acd = 0
	for j in range(o1 * o2):
		if r[j] == 1:
			count += 1
		if (j + 1) % o2 == 0:
			sum_array.append(count)
			if count >= o2 // +1:
				acd += 1
			count = 0
	if acd >= o1 // 2 + 1:
		m = 1
	else:
		m = 0
	if m == 0:
		for k in range(o2 - 1):
			totalcount = 0
			s = 0
			for j in range(k, o1 * o2, o2):
				sum_array[s] = sum_array[s] + r[j + o2] - r[j]
				if sum_array[s] >= o2 // 2 + 1:
					totalcount += 1
				s += 1
			if totalcount >= o1 // 2 + 1:
				m = 1
				break
	if m == 1:
		print(1)
	else:
		print(0)


def ans(l, o1, o2):
	i = 0
	n = len(l)
	l = l + l
	c = 0
	p = []
	while i < len(l):
		c += l[i]
		p += [c]
		i += 1
	i = 0
	while i < o2:
		(c1, c2) = (0, 0)
		j = i
		while j < n:
			if p[j + o2] - p[j] > o2 / 2:
				c1 += 1
			else:
				c2 += 1
			j += o2
		if c1 > c2:
			return 1
		i += 1
	return 0
t = int(input())
while t > 0:
	t -= 1
	(o1, o2) = map(int, input().split())
	l = list(map(int, input().split()))
	print(ans(l, o1, o2))


def solve(o1, o2, s):
	n = o1 * o2
	for i in range(1, n):
		s[i] = s[i - 1] + s[i]
	if (o1 + 1) / 2 * ((o2 + 1) / 2) > s[n - 1]:
		print('0')
		return
	for i in range(0, o2):
		sum_a = 0
		k = 2
		if i == 0:
			if s[i + o2 - 1] * 2 > o2:
				sum_a += 1
		else:
			k = 1
		for j in range(k, o1 + 1):
			a = (i + o2 * j - 1) % n
			b = (i + o2 * (j - 1) - 1) % n
			if a > b and (s[a] - s[b]) * 2 > o2 or (a < b and (s[n - 1] - s[b] + s[a]) * 2 > o2):
				sum_a += 1
		if sum_a * 2 > o1:
			print('1')
			return
	print('0')
t_cases = int(input())
t = 0
while t < t_cases:
	t += 1
	(a1, a2) = map(int, input().split())
	d = list(map(int, input().split()))
	solve(a1, a2, d)


import sys
t = int(sys.stdin.readline())
while t:
	(o1, o2) = [int(x) for x in sys.stdin.readline().split()]
	arr = [int(x) for x in sys.stdin.readline().split()]
	n = o1 * o2
	if o2 == 1 or o1 == 1:
		if sum(arr) > n // 2:
			print(1)
		else:
			print(0)
	else:
		res = [0] * n
		tmp_sum = sum(arr[-o2:])
		for i in range(o2):
			tmp_sum = tmp_sum - arr[-(o2 - i)] + arr[i]
			if tmp_sum > o2 // 2:
				res[i] = 1
		tmp_sum = sum(arr[:o2])
		for i in range(o2, n):
			tmp_sum = tmp_sum - arr[i - o2] + arr[i]
			res[i] = res[i - o2]
			if tmp_sum > o2 // 2:
				res[i] += 1
		if max(res) > o1 // 2:
			print(1)
		else:
			print(0)
	t = t - 1


num_cases = int(input())
for _ in range(num_cases):
	(num_states, districts_per_state) = map(int, input().strip().split())
	representatives = [int(c) for c in input().strip().split()]
	governors = []
	for i in range(0, len(representatives), districts_per_state):
		governors.append(sum(representatives[i:i + districts_per_state]))
	if sum(map(lambda x: 1 if x > districts_per_state // 2 else -1, governors)) > 0:
		print('1')
		continue
	for dist_idx in range(0, districts_per_state - 1):
		for state_idx in range(num_states):
			governors[state_idx] -= representatives[state_idx * districts_per_state + dist_idx]
			governors[state_idx - 1] += representatives[state_idx * districts_per_state + dist_idx]
		if sum(map(lambda x: 1 if x > districts_per_state // 2 else -1, governors)) > 0:
			print('1')
			break
	else:
		print('0')


import math
t = int(input())
while t != 0:
	t -= 1
	(n, m) = map(int, input().split())
	li = list(map(int, input().split()))
	check = []
	c = 0
	for i in range(m):
		if li[i] == 1:
			c += 1
	check = [0] * (n * m)
	check[0] = c
	for i in range(1, m * (n - 1) + 1):
		check[i] = check[i - 1]
		if li[i - 1] == 1:
			check[i] -= 1
		if li[i + m - 1] == 1:
			check[i] += 1
	for i in range(m * (n - 1) + 1, n * m):
		check[i] = check[i - 1]
		if li[i - 1] == 1:
			check[i] -= 1
		if li[(i + m - 1) % (n * m)] == 1:
			check[i] += 1
	ans = []
	for i in range(m):
		temp = []
		pos = i
		for j in range(n):
			temp.append(check[pos])
			pos += m
		ans.append(temp)
	ok = False
	for i in ans:
		lc = 0
		for j in i:
			if j >= (m + 1) // 2:
				lc += 1
		if lc >= (n + 1) // 2:
			ok = True
	if ok:
		print(1)
	else:
		print(0)


for t in range(int(input())):
	(o1, o2) = [int(i) for i in input().split()]
	d = [int(i) for i in input().split()]
	dbins = []
	i = 0
	for j in range(o1):
		l = []
		for k in range(o2):
			l.append(d[i])
			i += 1
		dbins.append(l)
	sums = [sum(d) for d in dbins]
	localplur = o2 // 2 + 1
	nationplur = o1 // 2 + 1
	wins = 0
	for s in sums:
		if s >= localplur:
			wins += 1
	if wins >= nationplur:
		print(1)
		continue
	found = False
	for i in range(o2 - 1):
		for j in range(o1 - 1):
			sums[j] += dbins[j + 1][i]
			sums[j] -= dbins[j][i]
		sums[-1] += dbins[0][i]
		sums[-1] -= dbins[-1][i]
		wins = 0
		for s in sums:
			if s >= localplur:
				wins += 1
		if wins >= nationplur:
			print(1)
			break
	else:
		print(0)


c = 1
cases = int(input())
while c <= cases:
	[n, m] = [int(i) for i in input().split()]
	d = [int(i) for i in input().split()]
	d += d[:m]
	dn = [0 for i in range(0, n)]
	ind = -1
	OZ = False
	for i in range(0, n * m):
		if i % m == 0:
			ind += 1
		dn[ind] += d[i]
	for i in range(0, m):
		zfc = 0
		ofc = 0
		for j in dn:
			if j > m - j:
				ofc += 1
			else:
				zfc += 1
		if ofc > zfc:
			OZ = True
			break
		for j in range(0, n):
			dn[j] = dn[j] - d[j * m + i] + d[(j + 1) * m + i]
	if OZ:
		print(1)
	else:
		print(0)
	c = c + 1


cases = int(input())
for case in range(cases):
	(states, dist) = map(int, input().strip().split())
	districts = list(map(int, input().strip().split()))
	districts = districts[:] + districts[:dist]
	distmaj = dist / 2
	statesmaj = states / 2
	nums = states * dist
	offsetSums = [0] * nums
	offsetSums[0] = sum(districts[:dist])
	for i in range(1, nums):
		offsetSums[i] = offsetSums[i - 1] - districts[i - 1] + districts[i - 1 + dist]
	offsetSums = list(map(lambda x: 1 if x > distmaj else 0, offsetSums))
	majorities = [0] * dist
	for i in range(dist):
		majorities[i] = [offsetSums[i + j * dist] for j in range(states)]
	presidents = list(map(lambda x: 1 if sum(x) > statesmaj else 0, majorities))
	print(max(presidents))


for _ in range(int(input())):
	(o1, o2) = map(int, input().split())
	arr = list(map(int, input().split()))
	(count1, count0) = ([0] * o1, [0] * o1)
	for i in range(o1):
		count1[i] = arr[i * o2:(i + 1) * o2].count(1)
		count0[i] = arr[i * o2:(i + 1) * o2].count(0)
	(win1, win0) = (0, 0)
	for i in range(o1):
		if count1[i] > count0[i]:
			win1 += 1
		else:
			win0 += 1
	if win1 > win0:
		print(1)
		continue
	for j in range(1, o2):
		for i in range(o1):
			(fi, li) = (i * o2 + j - 1, (i * o2 + j + o2 - 1) % (o1 * o2))
			if arr[fi] == 1:
				count1[i] -= 1
			else:
				count0[i] -= 1
			if arr[li] == 1:
				count1[i] += 1
			else:
				count0[i] += 1
		(win1, win2) = (0, 0)
		for i in range(o1):
			if count1[i] > count0[i]:
				win1 += 1
			else:
				win2 += 1
		if win1 > win2:
			print(1)
			break
	else:
		print(0)


t = int(input())
for t0 in range(t):
	s = [int(i) for i in input().strip().split()]
	(o1, o2) = (s[0], s[1])
	li = [int(i) for i in input().strip().split()]
	n = o1 * o2
	dp = [0 for i in range(n + 1)]
	for i in range(n):
		if li[i] == 0:
			dp[i + 1] = dp[i]
		else:
			dp[i + 1] = dp[i] + 1
	fl = 0
	ct = 0
	mid = (o2 + 1) // 2
	mnd = (o1 + 1) // 2
	noo = 0
	noz = 0
	cal = n - o2 - o2 + 1
	while ct < o2:
		tmp = ct
		fl = 0
		noo = 0
		noz = 0
		while tmp < cal + ct:
			if dp[tmp + o2] - dp[tmp] >= mid:
				noo += 1
			else:
				noz += 1
			tmp += o2
			if noo == mnd:
				fl = 1
				break
			elif noz == mnd:
				fl = 2
				break
		if fl == 1:
			break
		elif fl == 2:
			ct += 1
		else:
			if tmp == n - o2:
				if dp[tmp + o2] - dp[tmp] >= mid:
					fl = 1
					break
			else:
				tmpr = dp[n] - dp[tmp] + dp[ct]
				if tmpr >= mid:
					fl = 1
					break
			ct += 1
	if fl == 1:
		print(1)
	else:
		print(0)


flag_debug = True

def read(type=int):
	return type(input())

def read_arr(type=int):
	return [type(token) for token in input().split()]

def debug(*args):
	if flag_debug:
		print(args)

def check(C, s, d):
	count = 0
	for i in range(s):
		if C[i] >= (d + 1) // 2:
			count += 1
			if count >= (s + 1) // 2:
				return 1
	return 0

def solve(s, d, A):
	C = [0] * s
	for i in range(s):
		for j in range(d):
			C[i] += A[i * d + j]
	c = 0
	for j in range(d):
		for k in range(s):
			C[k] += A[(k + 1) % s * d + j] - A[k * d + j]
		c = check(C, s, d)
		if c == 1:
			break
	return c

def run():
	t = read()
	for i in range(t):
		(s, d) = read_arr()
		A = read_arr()
		print(solve(s, d, A))
run()


cases = int(input())
while cases:
	cases -= 1
	[states, districts] = list(map(int, input().split()))
	polls = list(map(int, input().split()))
	districtWins = [0] * len(polls)
	stateWins = [0] * len(polls)
	minDistrict = districts // 2 + 1
	minState = states // 2 + 1
	polls.extend(polls[:districts - 1])
	oneWins = False
	if states == 1 or districts == 1:
		oneWins = True if polls[:states * districts].count(1) >= states * districts / 2 else False
	else:
		initialSum = sum(polls[:districts])
		districtWins[0] = initialSum
		stateWins[0] = 1 if districtWins[0] >= minDistrict else 0
		if stateWins[0] >= minState:
			oneWins = True
		else:
			for i in range(1, states * districts):
				districtWins[i] = districtWins[i - 1] - polls[i - 1] + polls[i + districts - 1]
				stateWins[i] = (0 if i < districts else stateWins[i - districts]) + (1 if districtWins[i] >= minDistrict else 0)
				if stateWins[i] >= minState:
					oneWins = True
					break
	if oneWins:
		print(1)
	else:
		print(0)


def checkpresident(o1, o2, arr=None, sumarr=None):
	if arr == None:
		arr = []
	if sumarr == None:
		sumarr = []
	for i in range(o2):
		count = [0, 0]
		x = i
		for j in range(o1):
			if x < o2:
				if sumarr[x] - 0 + sumarr[len(arr) - 1] - sumarr[len(arr) - 1 - (o2 - (x + 1))] >= (o2 + 1) // 2:
					count[1] += 1
				else:
					count[0] += 1
			elif sumarr[x] - sumarr[x - o2] >= (o2 + 1) // 2:
				count[1] += 1
			else:
				count[0] += 1
			x += o2
		if count[1] > count[0]:
			return 1
	return 0

def problem3():
	t = int(input())
	for T in range(t):
		temp = input()
		(o1, o2) = [int(i) for i in temp.split()]
		temp = input()
		arr = [int(i) for i in temp.split()]
		sumarr = arr
		for i in range(1, len(arr)):
			sumarr[i] = sumarr[i - 1] + arr[i]
		print(checkpresident(o1, o2, arr, sumarr))
problem3()


t = int(input())
for i in range(t):
	flag = 0
	(o1, o2) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a = a + a[:o2 - 1]
	b = [0] * o2
	ones = 0
	ones = sum(a[:o2])
	if ones > o2 / 2:
		b[0] = 1
	for j in range(o2, len(a)):
		ones = ones + a[j] - a[j - o2]
		if ones > o2 / 2:
			b[(j + 1) % o2] += 1
	if any((i > o1 / 2 for i in b)):
		print(1)
	else:
		print(0)


t = int(input())
for i in range(t):
	a = []
	(o1, o2) = map(int, input().split())
	n = o1 * o2
	a.extend(map(int, input().split()))
	b = []
	s = 0
	for j in range(o2):
		s += a[j]
	b.append(s)
	for j in range(1, n):
		s = s - a[j - 1] + a[(j + o2 - 1) % n]
		b.append(s)
	ans = 0
	for i in range(o2):
		f = 0
		for j in range(o1):
			if b[j * o2 + i] > o2 // 2:
				f += 1
		if f > o1 // 2:
			ans = 1
			break
	print(ans)


def read_input():
	t = int(input())
	for _ in range(t):
		(o1, o2) = input().strip().split()
		(o1, o2) = (int(o1), int(o2))
		l = input().strip().split()
		l[0] = int(l[0])
		for i in range(1, o1 * o2):
			l[i] = l[i - 1] + int(l[i])
		flag = False
		for i in range(0, o2):
			bits = calculate(i, o1, o2, l)
			if sum(bits) > len(bits) / 2:
				flag = True
				break
		if flag:
			print(1)
		else:
			print(0)

def calculate(i, o1, o2, l):
	bit = [0 for _ in range(o1)]
	j = i
	for k in range(o1):
		if j == 0:
			if l[j + o2 - 1] > o2 / 2:
				bit[k] = 1
		elif j + o2 - 1 < o1 * o2:
			if l[j + o2 - 1] - l[j - 1] > o2 / 2:
				bit[k] = 1
		elif l[o1 * o2 - 1] - l[j - 1] + l[o2 - (o1 * o2 - j)] > o2 / 2:
			bit[k] = 1
		j += o2
	return bit
read_input()


t = int(input())
while t > 0:
	(o1, o2) = map(int, input().split())
	n = o1 * o2
	a = [int(i) for i in input().split()]
	sum = []
	sum.append(a[0])
	for i in range(1, n):
		sum.append(sum[i - 1] + a[i])
	ok = False
	for i in range(0, o2):
		one = 0
		zero = 0
		for k in range(0, o1):
			cnt = 0
			j = k * o2 + i
			if j + o2 - 1 >= n:
				jj = (j + o2 - 1) % n
				if j == 0:
					cnt = sum[n - 1] + sum[jj]
				else:
					cnt = sum[n - 1] - sum[j - 1] + sum[jj]
			else:
				jj = (j + o2 - 1) % n
				if j == 0:
					cnt = sum[jj]
				else:
					cnt = sum[jj] - sum[j - 1]
			if cnt > o2 - cnt:
				one += 1
			else:
				zero += 1
		if one > zero:
			ok = True
			break
	if ok == True:
		print(1)
	else:
		print(0)
	t -= 1


t = int(input())
arr_st_pos = []

def cal(i, size, all_dist_rep):
	summ = 0
	while i < size:
		summ += all_dist_rep[i]
		i += 1
	return summ
i = 0
while i < 1000000:
	arr_st_pos.append(-1)
	i += 1
while t:
	t -= 1
	o1o2 = [int(x) for x in input().split()]
	o1 = o1o2[0]
	o2 = o1o2[1]
	n = o1 * o2
	all_dist_rep = [int(x) for x in input().split()]
	ref_table = set([])
	i = 0
	val = cal(i, o2, all_dist_rep)
	dist_maj = o2 // 2
	if val > dist_maj:
		arr_st_pos[0] = 0
	i = 1
	while i < n:
		new_val = val - all_dist_rep[i - 1] + all_dist_rep[(i + o2 - 1) % n]
		if new_val > dist_maj:
			arr_st_pos[i] = i
		else:
			arr_st_pos[i] = -1
		val = new_val
		i += 1
	leng_pos_tab = len(arr_st_pos)
	j = 0
	flag = 1
	cnt = 0
	state_maj = o1 // 2
	while j < leng_pos_tab and (not cnt > state_maj):
		st = arr_st_pos[j]
		if st == -1:
			j += 1
			continue
		cnt = 1
		arr_st_pos[st] = -1
		i = (st + o2) % n
		while i != st and (not cnt > state_maj):
			if arr_st_pos[i] != -1:
				arr_st_pos[i] = -1
				cnt += 1
			i = (i + o2) % n
		j += 1
	if j < leng_pos_tab:
		print('1')
	else:
		print('0')


t = int(input().strip(' '))
for _ in range(t):
	(o1, o2) = map(int, input().strip(' ').split(' '))
	n = o1 * o2
	array = list(input().strip(' ').split(' '))
	one = zero = 0
	for i in range(o2):
		if array[i] == '0':
			zero += 1
		else:
			one += 1
	num = list()
	if one > zero:
		num.append(1)
	else:
		num.append(0)
	for i in range(n - 1):
		if array[(i + o2) % n] == '0':
			zero += 1
		else:
			one += 1
		if array[i] == '0':
			zero -= 1
		else:
			one -= 1
		if one > zero:
			num.append(1)
		else:
			num.append(0)
	for i in range(o2):
		one = 0
		zero = 0
		for j in range(i, n, o2):
			if num[j] == 1:
				one += 1
			else:
				zero += 1
		if one > zero:
			print(1)
			break
	else:
		print(0)


from collections import deque
t = int(input())
ans = []
for i in range(t):
	(o1, o2) = list(map(int, input().split()))
	d = list(map(int, input().split()))
	list_of_states = [0 for j in range(len(d))]
	win_que = deque()
	num_zer = 0
	num_one = 0
	for j in range(o2):
		win_que.append(d[j])
		if d[j] == 0:
			num_zer += 1
		else:
			num_one += 1
	if num_one > num_zer:
		list_of_states[0] = 1
	for j in range(1, len(d)):
		ele = win_que.popleft()
		if ele == 0:
			num_zer -= 1
		else:
			num_one -= 1
		if j <= len(d) - o2:
			if d[j + o2 - 1] == 0:
				num_zer += 1
			else:
				num_one += 1
			win_que.append(d[j + o2 - 1])
		else:
			if d[o2 - (len(d) - j) - 1] == 0:
				num_zer += 1
			else:
				num_one += 1
			win_que.append(d[o2 - (len(d) - j) - 1])
		if j >= o2:
			if num_one > num_zer:
				list_of_states[j] = list_of_states[j - o2] + 1
			else:
				list_of_states[j] = list_of_states[j - o2]
		elif num_one > num_zer:
			list_of_states[j] = 1
	max_count = 0
	for j in range(len(d)):
		if list_of_states[j] > max_count:
			max_count = list_of_states[j]
	if max_count >= (o1 + 1) // 2:
		ans.append(1)
	else:
		ans.append(0)
for x in ans:
	print(x)


T = int(input())
for t in range(T):
	(o1, o2) = map(int, input().strip().split())
	A = list(map(int, input().strip().split()))
	A = A + A[:o2 - 1]
	N = o1 * o2
	ans = 0
	if o2 == 1:
		if A.count(1) > A.count(0):
			ans = 1
	else:
		Z = [0] * (N + o2)
		O = [0] * (N + o2)
		for i in range(N + o2 - 1):
			if A[i] & 1:
				O[i + 1] = O[i] + 1
				Z[i + 1] = Z[i]
			else:
				O[i + 1] = O[i]
				Z[i + 1] = Z[i] + 1
		for i in range(o2):
			(ones, zeros) = (0, 0)
			for j in range(i, N, o2):
				z = Z[j + o2] - Z[j]
				o = O[j + o2] - O[j]
				if o > z:
					ones += 1
				else:
					zeros += 1
			if ones > zeros:
				ans = 1
				break
	print(ans)


t = int(input())

def cal(i, size, all_dist_rep):
	summ = 0
	while i < size:
		summ += all_dist_rep[i]
		i += 1
	return summ
while t:
	t -= 1
	o1o2 = [int(x) for x in input().split()]
	o1 = o1o2[0]
	o2 = o1o2[1]
	n = o1 * o2
	all_dist_rep = [int(x) for x in input().split()]
	ref_table = set([])
	arr_st_pos = []
	i = 0
	val = cal(i, o2, all_dist_rep)
	dist_maj = o2 // 2
	if val > dist_maj:
		arr_st_pos.append(0)
	i = 1
	while i < n:
		new_val = val - all_dist_rep[i - 1] + all_dist_rep[(i + o2 - 1) % n]
		if new_val > dist_maj:
			arr_st_pos.append(i)
		val = new_val
		i += 1
	leng_pos_tab = len(arr_st_pos)
	state_maj = o1 // 2
	arr_cnt = []
	for i in range(0, o2):
		arr_cnt.append(0)
	for i in range(0, leng_pos_tab):
		arr_cnt[arr_st_pos[i] % o2] = arr_cnt[arr_st_pos[i] % o2] + 1
	arr_cnt.sort()
	if arr_cnt[o2 - 1] > state_maj:
		print('1')
	else:
		print('0')


for t in range(0, int(input())):
	arr = [int(i) for i in input().split()]
	(o, p, f) = (arr[0], arr[1], True)
	arr = [int(i) for i in input().split()]
	lst = [0 for i in range(0, o * p)]
	(one, zer, n) = (0, 0, o * p)
	for i in range(0, p):
		if arr[i] == 0:
			zer += 1
		else:
			one += 1
	if zer > one:
		lst[0] = 0
	else:
		lst[1] = 1
	i = 1
	while i < n:
		if arr[(i - 1 + n) % n] == 0:
			zer -= 1
		else:
			one -= 1
		if arr[(i + p - 1) % n] == 0:
			zer += 1
		else:
			one += 1
		if zer > one:
			lst[i] = 0
		else:
			lst[i] = 1
		i += 1
	f = True
	if p == 1:
		for i in range(0, n):
			lst[i] = arr[i]
	for i in range(0, p):
		(zer, one, j, cn) = (0, 0, i, 0)
		while cn < o:
			if lst[j] == 0:
				zer += 1
			else:
				one += 1
			cn += 1
			j = (j + p) % n
		if one > zer:
			print(1)
			f = False
			break
	if f:
		print(0)


def f(N, M, A):
	pref_sum = [0]
	for i in range(N * M):
		pref_sum.append(pref_sum[-1] + A[i])
	for i in range(1, M + 1):
		j = i
		cnt = 0
		while j + M <= N * M + 1:
			if pref_sum[j + M - 1] - pref_sum[j - 1] > M / 2:
				cnt += 1
			if cnt > N / 2:
				print(1)
				return
			j += M
		if j < N * M:
			l = pref_sum[N * M] - pref_sum[j - 1] + pref_sum[i]
			if l > M / 2:
				cnt += 1
			if cnt > N / 2:
				print(1)
				return
	print(0)
	return
T = int(input())
while T > 0:
	T -= 1
	(N, M) = [int(x) for x in input().strip().split()]
	A = [int(x) for x in input().strip().split()]
	f(N, M, A)


def is_pres(st, l1, l2):
	cnt = 0
	for i in st:
		if i > l2 // 2:
			cnt += 1
	return cnt > l1 // 2
for _ in range(int(input())):
	(o1, o2) = map(int, input().split())
	n = o1 * o2
	a = list(map(int, input().split()))
	a.extend(a[:o2])
	result = 0
	c = a.count(1)
	b = []
	for i in range(o1):
		b.append(sum(a[i * o2:(i + 1) * o2]))
	if is_pres(b, o1, o2):
		result = 1
	else:
		for i in range(o2 - 1):
			for j in range(o1):
				b[j] -= a[i + j * o2]
				b[j] += a[i + (j + 1) * o2]
			if is_pres(b, o1, o2):
				result = 1
				break
	print(result)