ChthollyNotaSeniorious received a special gift from AquaMoon: $n$ binary arrays of length $m$. AquaMoon tells him that in one operation, he can choose any two arrays and any position $pos$ from $1$ to $m$, and swap the elements at positions $pos$ in these arrays.

He is fascinated with this game, and he wants to find the minimum number of operations needed to make the numbers of $1$s in all arrays the same. He has invited you to participate in this interesting game, so please try to find it!

If it is possible, please output specific exchange steps in the format described in the output section. Otherwise, please output $-1$.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \leq t \leq 2\cdot 10^4$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $2 \leq m \leq 10^5$).

The $i$-th of the following $n$ lines contains $m$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$ $(0 \le a_{i, j} \le 1)$  — the elements of the $i$-th array.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.


-----Output-----

For each test case, if the objective is not achievable, output $-1$.

Otherwise, in the first line output $k$ $(0 \le k \le mn)$  — the minimum number of operations required.

The $i$-th of the following $k$ lines should contain $3$ integers, $x_i, y_i, z_i$ $(1 \le x_i, y_i \le n, 1 \le z_i \le m)$, which describe an operation that swap $a_{x_i, z_i}, a_{y_i, z_i}$: swap the $z_i$-th number of the $x_i$-th and $y_i$-th arrays.


-----Examples-----

Input
3
3 4
1 1 1 0
0 0 1 0
1 0 0 1
4 3
1 0 0
0 1 1
0 0 1
0 0 0
2 2
0 0
0 1
Output
1
2 1 1
1
4 2 2
-1


-----Note-----

In the first test case, it's enough to do a single operation: to swap the first element in the second and the first rows. The arrays will become $[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$, each of them contains exactly two $1$s.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Amortized analysis

Implementation

Greedy algorithms

Complete search
Skill types: Complete search

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	a = []
	num = [0] * n
	for i in range(n):
		a.append([int(i) for i in input().split()])
		num[i] = a[i].count(1)
	count = sum(num)
	if count % n:
		print(-1)
		continue
	count //= n
	mm = 0
	for i in num:
		if i - count > 0:
			mm += i - count
	print(mm)
	(i, j) = (0, 0)
	while True:
		while i < n and num[i] <= count:
			i += 1
		while j < n and num[j] >= count:
			j += 1
		if i >= n or j >= n:
			break
		m = min(num[i] - count, count - num[j])
		num[i] -= m
		num[j] += m
		f = 0
		while m:
			if a[i][f] == 1 and a[j][f] == 0:
				a[i][f] = 0
				a[j][f] = 1
				print(i + 1, j + 1, f + 1)
				m -= 1
			f += 1


for tc in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	c1 = []
	for i in range(n):
		c1.append(l[i].count(1))
	exp1 = sum(c1) // n
	exp0 = m - exp1
	if sum(c1) % n != 0:
		print(-1)
		continue
	elif c1.count(exp1) == n:
		print(0)
		continue
	more = []
	less = []
	for i in range(n):
		if c1[i] > exp1:
			more.append(i)
		elif c1[i] < exp1:
			less.append(i)
	k = 0
	count = 0
	res = []
	i = 0
	while i < len(more):
		for j in range(m):
			if i >= len(more):
				break
			if l[more[i]][j] == 1 and l[less[k]][j] == 0:
				count += 1
				res.append([more[i] + 1, less[k] + 1, j + 1])
				l[more[i]][j] = 0
				l[less[k]][j] = 1
				c1[less[k]] += 1
				c1[more[i]] -= 1
				if c1[less[k]] == exp1:
					k += 1
				if c1[more[i]] == exp1:
					i += 1
	print(count)
	for i in res:
		print(i[0], end=' ')
		print(i[1], end=' ')
		print(i[2], end=' ')
		print()


for i in range(int(input())):
	(rows, cols) = map(int, input().split())
	mat = []
	ones_arr = []
	total_ones = 0
	for i in range(rows):
		arr = list(map(int, input().split()))
		mat.append(arr)
		ones_count = arr.count(1)
		ones_arr.append(ones_count)
		total_ones += ones_count
	avg = total_ones / rows
	if avg != int(avg):
		print(-1)
	else:
		ava = int(avg)
		ans = []
		for j in range(cols):
			extra = []
			for i in range(rows):
				if ones_arr[i] > avg and mat[i][j] == 1:
					extra.append(i)
			for i in range(rows):
				if ones_arr[i] < avg and mat[i][j] == 0 and (len(extra) > 0):
					donor = extra.pop()
					ans.append([i + 1, donor + 1, j + 1])
					ones_arr[i] += 1
					ones_arr[donor] -= 1
		print(len(ans))
		for i in ans:
			print(*i)


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().strip().split()]
	a = []
	count = 0
	stri_1 = [[0, i] for i in range(n)]
	for i in range(n):
		temp = [int(i) for i in input().strip().split()]
		a.append(temp)
		for j in range(m):
			if temp[j] == 1:
				stri_1[i][0] += 1
				count += 1
	if count % n != 0:
		print(-1)
	else:
		ans = []
		val = count // n
		stri_1.sort(reverse=True)
		i = 0
		j = n - 1
		while j > i:
			for k in range(m):
				if stri_1[i][0] == val:
					i += 1
					break
				if stri_1[j][0] == val:
					j -= 1
					break
				if a[stri_1[i][1]][k] == 1 and a[stri_1[j][1]][k] == 0:
					ans.append([stri_1[i][1] + 1, stri_1[j][1] + 1, k + 1])
					a[stri_1[i][1]][k] = 0
					a[stri_1[j][1]][k] = 1
					stri_1[i][0] -= 1
					stri_1[j][0] += 1
			if stri_1[i][0] == val:
				i += 1
			if stri_1[j][0] == val:
				j -= 1
		print(len(ans))
		for x in ans:
			print(*x)


t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	a = []
	aux = []
	up = []
	down = []
	ss = 0
	for i in range(n):
		c = 0
		l = list(map(int, input().split()))
		a.append(l)
		for i in range(m):
			if l[i] == 1:
				c += 1
		aux.append(c)
	s = sum(aux)
	if s % n != 0:
		print(-1)
	else:
		for i in range(n):
			if aux[i] == s / n:
				pass
			elif aux[i] < s / n:
				down.append(i)
			else:
				ss += aux[i] - s / n
				up.append(i)
		print(int(ss))
		i = 0
		o = 0
		while i < len(up):
			flag = 0
			while o < len(down) and flag == 0:
				fflag = 0
				while aux[up[i]] > int(s / n) and aux[down[o]] < int(s / n):
					for j in range(m):
						if a[up[i]][j] == 1 and a[down[o]][j] == 0:
							a[up[i]][j] = 0
							a[down[o]][j] = 1
							print(up[i] + 1, down[o] + 1, j + 1)
							aux[up[i]] -= 1
							aux[down[o]] += 1
						if aux[up[i]] == int(s / n):
							flag = 1
						if aux[down[o]] == int(s / n):
							fflag = 1
						if flag == 1 or fflag == 1:
							break
				if flag == 1:
					i += 1
				if fflag == 1:
					o += 1


import sys

def parse():
	t = int(sys.stdin.readline())
	for i in range(t):
		(n, m) = list(map(int, sys.stdin.readline().split()))
		matrix = []
		count_rows = [0] * n
		actions_count = 0
		actions = []
		for j in range(n):
			arr = list(map(int, sys.stdin.readline().split()))
			matrix.append(arr)
			count_rows[j] = sum(arr)
		ones_count = sum(count_rows)
		if ones_count % n != 0:
			print('-1')
			continue
		ones_row_count = ones_count // n
		less_idx = 0
		large_idx = 0
		while True:
			while less_idx < n and count_rows[less_idx] >= ones_row_count:
				less_idx += 1
			while large_idx < n and count_rows[large_idx] <= ones_row_count:
				large_idx += 1
			if less_idx == n:
				break
			for j in range(m):
				if matrix[large_idx][j] == 1 and matrix[less_idx][j] == 0:
					matrix[large_idx][j] = 0
					matrix[less_idx][j] = 1
					count_rows[large_idx] -= 1
					count_rows[less_idx] += 1
					actions.append((large_idx + 1, less_idx + 1, j + 1))
					actions_count += 1
					if count_rows[large_idx] == ones_row_count or count_rows[less_idx] == ones_row_count:
						break
		print(actions_count)
		if actions_count > 0:
			for action_idx in range(actions_count):
				print(*actions[action_idx])
parse()


for jj in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	tm = []
	tot = 0
	for i in range(n):
		arr = input().split()
		a = arr.count('1')
		arr = [a] + arr + [i + 1]
		tm.append(arr)
		tot += a
	if tot % n != 0:
		print(-1)
		continue
	tm.sort()
	(i, j) = (0, n - 1)
	ans = []
	p = tot // n
	while i < j:
		a = tm[i][0]
		b = tm[j][0]
		if a == b == p:
			i += 1
			j -= 1
			continue
		elif a == p:
			i += 1
			continue
		elif b == p:
			j -= 1
			continue
		k = min(p - a, b - p)
		for ii in range(1, m + 1):
			if k == 0:
				break
			if tm[j][ii] == '1':
				if tm[i][ii] == '0':
					(tm[j][ii], tm[i][ii]) = (tm[i][ii], tm[j][ii])
					tm[i][0] += 1
					tm[j][0] -= 1
					ans.append((tm[i][-1], tm[j][-1], ii))
					k -= 1
	print(len(ans))
	for i in ans:
		print(*i)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	nums = []
	cnt = []
	for _ in range(n):
		lin = list(map(int, input().split()))
		cnt.append(lin.count(1))
		nums.append(lin)
	sums = sum(cnt)
	h = sums // n
	if sums % n != 0:
		print(-1)
		continue
	for i in range(n):
		cnt[i] = cnt[i] - h
	has = [[] for _ in range(m)]
	need = [[] for _ in range(m)]
	for i in range(n):
		for j in range(m):
			if cnt[i] > 0 and nums[i][j] == 1:
				has[j].append(i)
			elif cnt[i] < 0 and nums[i][j] == 0:
				need[j].append(i)
	cao = []
	for i in range(m):
		bur = cur = 0
		while bur < len(has[i]) and cur < len(need[i]):
			if cnt[has[i][bur]] == 0:
				bur += 1
			elif cnt[need[i][cur]] == 0:
				cur += 1
			else:
				cao.append([has[i][bur], need[i][cur], i])
				cnt[has[i][bur]] -= 1
				cnt[need[i][cur]] += 1
				bur += 1
				cur += 1
	print(len(cao))
	for i in cao:
		print(i[0] + 1, i[1] + 1, i[2] + 1)


t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	lst = [[int(k) for k in input().split()] for j in range(n)]
	sums = []
	for l in lst:
		sums.append(sum(l))
	if sum(sums) % n != 0:
		print(-1)
		continue
	even_sum = sum(sums) // n
	ops = []
	for j in range(m):
		ones = []
		for k in range(n):
			if sums[k] > even_sum and lst[k][j] == 1:
				ones.append(k)
		for k in range(n):
			if sums[k] < even_sum and lst[k][j] == 0 and (len(ones) > 0):
				pos = ones.pop(0)
				sums[pos] -= 1
				sums[k] += 1
				(lst[k][j], lst[pos][j]) = (1, 0)
				ops.append(f'{pos + 1} {k + 1} {j + 1}')
	print(len(ops))
	for j in ops:
		print(j)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = []
	ct = []
	for x in range(n):
		a = list(map(int, input().split()))
		l.append(a)
		cnt = 0
		for y in a:
			if y == 1:
				cnt += 1
		ct.append(cnt)
	oct = sum(ct)
	if oct % n != 0:
		print(-1)
	else:
		oct = int(oct / n)
		inc = dict()
		drc = dict()
		for i in range(n):
			if ct[i] > oct:
				inc[i] = ct[i] - oct
			elif ct[i] < oct:
				drc[i] = oct - ct[i]
		x = list(inc.keys())
		y = list(drc.keys())
		x1 = 0
		y1 = 0
		print(sum(list(inc.values())))
		while x1 < len(x) and y1 < len(y):
			for j in range(m):
				if l[x[x1]][j] == 1 and l[y[y1]][j] == 0:
					print(x[x1] + 1, y[y1] + 1, j + 1)
					l[x[x1]][j] = 0
					l[y[y1]][j] = 1
					f = 0
					inc[x[x1]] -= 1
					drc[y[y1]] -= 1
					if inc[x[x1]] == 0:
						x1 += 1
						f = 1
					if drc[y[y1]] == 0:
						y1 += 1
						f = 1
					if f:
						break
			if x1 == len(x) or y1 == len(y):
				break


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	d = {}
	ts = 0
	for i in range(n):
		a.append(list(map(int, input().split())))
		d[i] = sum(a[i])
		ts += d[i]
	if ts % n != 0:
		print(-1)
		continue
	am = ts // n
	ans = []
	for i in range(m):
		mx = []
		mn = []
		for j in range(n):
			if d[j] > am and a[j][i] == 1:
				mx.append(j)
			elif d[j] < am and a[j][i] == 0:
				mn.append(j)
		for k in range(min(len(mx), len(mn))):
			ans.append((mx[k] + 1, mn[k] + 1, i + 1))
			d[mx[k]] -= 1
			d[mn[k]] += 1
	print(len(ans))
	for i in ans:
		print(*i)