There is a building with $N$ floors (numbered $1$ through $N$ from bottom to top); on each floor, there are $M$ windows (numbered $1$ through $M$ from left to right). Let's denote the $j$-th window on the $i$-th floor by $(i, j)$.
All windows in the building need to be cleaned one by one in a specific order. You are given this order as a matrix $A$ with $N$ rows and $M$ columns; for each valid $i$ and $j$, the window $(i, j)$ must be cleaned on the $A_{N-i+1,j}$-th turn. 
Whenever we clean a window $(i, j)$, it becomes clean, but the dirty water used for cleaning it flows down to windows $(i-1, j-1)$, $(i-1, j)$ and $(i-1, j+1)$ (more precisely, to all of these windows which exist), so these windows become dirty again. Then, the water flows further down, so the same applies for other windows below: whenever a window $(i, j)$ becomes dirty, windows $(i-1, j-1)$, $(i-1, j)$ and $(i-1, j+1)$ become dirty as well. For example, cleaning a window $(5, 3)$ will make the window $(3, 2)$ dirty. The next window is cleaned only after water flows down completely. Note that each window is cleaned only once and there may be dirty windows at the end.
For each window, determine whether it will be clean after the cleaning process ends.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $M$. 
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains $M$ space-separated integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}$.

-----Output-----
For each test case, print $N$ lines; each of them should contain a string with length $M$. For each valid $i$ and $j$, the $j$-th character on the $i$-th line should be '1' if the window $(N-i+1, j)$ is clean or '0' if it is dirty.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N, M \le 10^3$
- $1 \le A_{i, j} \le N \cdot M$ for each valid $i, j$
- the elements of the matrix $A$ are pairwise distinct
- the sum of $N \cdot M$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $N, M \le 25$
- the sum of $N \cdot M$ over all test cases does not exceed $625$
Subtask #2 (50 points): original constraints

-----Example Input-----
1
3 4
1 3 7 10
9 2 4 11
8 12 5 6 

-----Example Output-----
1111
1001
0100

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	arr = []
	ans = []
	for i in range(0, n):
		in_arr = list(map(int, input().split()))
		if i == 0:
			x = '1' * m
		else:
			x = ''
			for j in range(0, m):
				arr2 = [0] * m
				if j == 0:
					maxv = max(ans[i - 1][0], ans[i - 1][1])
				elif j == m - 1:
					maxv = max(ans[i - 1][m - 2], ans[i - 1][m - 1])
				else:
					maxv = max(ans[i - 1][j - 1], ans[i - 1][j], ans[i - 1][j + 1])
				if maxv > in_arr[j]:
					in_arr[j] = maxv
					x = x + '0'
				else:
					x = x + '1'
		ans.append(in_arr)
		arr.append(x)
	for i in range(0, n):
		print(arr[i])


def arr_str(arr):
	strr = ''
	for i in arr:
		strr += str(i)
	return strr
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = [0] * n
	for i in range(n):
		temp = [0]
		B = [int(i) for i in input().split()]
		temp.extend(B)
		temp.append(0)
		A[i] = temp
	ans = [[0 for i in range(m)] for j in range(n)]
	dp = [[0 for i in range(m + 2)] for j in range(n)]
	for i in range(m):
		dp[0][i + 1] = A[0][i + 1]
	for i in range(1, n):
		for j in range(1, m + 1):
			temp = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])
			if temp > A[i][j]:
				ans[i - 1][j - 1] = 0
			else:
				ans[i - 1][j - 1] = 1
			temp = max(temp, A[i][j])
			dp[i][j] = temp
	tem = [1] * m
	print(arr_str(tem), end='\n')
	for i in range(n - 1):
		print(arr_str(ans[i]), end='\n')


R = lambda : map(int, input().split())
(t,) = R()
for _ in range(t):
	(n, m) = R()
	a = b = [0] * m
	for _ in range(n):
		a = list(map(max, [0] + a, a, a[1:] + [0], [0] + b, b, b[1:] + [0]))
		b = list(R())
		print(''.join(('01'[x < y] for (x, y) in zip(a, b))))


from sys import stdin
t = int(stdin.readline())
while t:
	(n, m) = map(int, stdin.readline().split())
	a = []
	k = [[1 for _ in range(m)] for __ in range(n)]
	for _ in range(n):
		a.append(list(map(int, stdin.readline().split())))
	dp = [[a[i][_] for _ in range(m)] for i in range(n)]
	for i in range(1, n):
		for j in range(m):
			if j == m - 1:
				dp[i][j] = max(0, max(dp[i - 1][j - 1], dp[i - 1][j]))
			elif j == 0:
				dp[i][j] = max(0, max(dp[i - 1][j], dp[i - 1][j + 1]))
			else:
				dp[i][j] = max(0, max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]))
			if dp[i][j] > a[i][j]:
				k[i][j] = 0
			else:
				k[i][j] = 1
				dp[i][j] = a[i][j]
	for i in range(n):
		for j in range(m):
			print(k[i][j], end='')
		print()
	t -= 1


try:
	t = int(input())
	while t > 0:
		t -= 1
		(n, m) = list(map(int, input().split()))
		a = [list(map(int, input().split())) for _ in range(n)]
		dp = [[0 for _ in range(m)] for _ in range(n)]
		ans = [['0' for _ in range(m)] for _ in range(n)]
		for i in range(n):
			for j in range(m):
				if i - 1 < n:
					if 0 <= j - 1 and j + 1 < m:
						dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])
					elif j == 0:
						dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + 1])
					elif j == m - 1:
						dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j])
				if dp[i][j] > a[i][j]:
					ans[i][j] = '0'
				else:
					ans[i][j] = '1'
					dp[i][j] = a[i][j]
		for i in ans:
			print(''.join(i))
except:
	pass


import numpy as np
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	order = np.zeros((n * m, 2), dtype=np.uint8)
	state = np.ones((n, m), dtype=np.uint8) * 2
	for i in range(n):
		j = 0
		for e in map(int, input().split()):
			order[e - 1] = (i, j)
			j += 1
	for i0 in range(n * m - 1, -1, -1):
		(i, j) = order[i0]
		if state[i, j] == 2:
			j_start = j_end = j
			state[i, j] = 1
			while i < n - 1:
				i += 1
				j_start = max(0, j_start - 1)
				j_end = min(m, j_end + 1)
				state[i, j_start:j_end + 1] &= 1
	for i in range(n):
		print(''.join(map(str, state[i])))


t = int(input())
while t:
	(n, m) = list(map(int, input().split()))
	building = []
	res = []
	for i in range(0, n):
		building.append(list(map(int, input().split())))
		res.append([1] * m)
		for j in range(0, m):
			max_element = 0
			if i - 1 >= 0 and building[i][j] < building[i - 1][j] or (i - 1 >= 0 and j - 1 >= 0 and (building[i][j] < building[i - 1][j - 1])) or (i - 1 >= 0 and j + 1 < m and (building[i][j] < building[i - 1][j + 1])):
				res[i][j] = 0
			if i - 1 >= 0:
				max_element = max(max_element, building[i - 1][j])
			if i - 1 >= 0 and j - 1 >= 0:
				max_element = max(max_element, building[i - 1][j - 1])
			if i - 1 >= 0 and j + 1 < m:
				max_element = max(max_element, building[i - 1][j + 1])
			building[i][j] = max(building[i][j], max_element)
	for i in range(0, n):
		for j in range(0, m):
			print(res[i][j], end='')
		print()
	t -= 1


from collections import defaultdict
t = int(input())
for _ in range(0, t):
	(r, c) = list(map(int, input().split()))
	a = []
	for _ in range(r):
		a.append(list(map(int, input().split())))
	d = defaultdict(lambda : 0)
	for i in range(1, r):
		for j in range(0, c):
			if j - 1 >= 0:
				d[i, j] = max(a[i - 1][j - 1], d[i, j], d[i - 1, j - 1])
			if j >= 0:
				d[i, j] = max(a[i - 1][j], d[i, j], d[i - 1, j])
			if j + 1 < c:
				d[i, j] = max(a[i - 1][j + 1], d[i, j], d[i - 1, j + 1])
	for i in range(0, r):
		if i != 0:
			print()
		for j in range(0, c):
			if a[i][j] > d[i, j]:
				print(1, end='')
			else:
				print(0, end='')
		if i == r - 1:
			print()


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	matrix = []
	for k3 in range(n):
		matrix.append(list(map(int, input().split())))
	output = []
	for k2 in range(n):
		output.append([[1, -1] for k in range(m)])
	for i in range(1, n):
		for j in range(m):
			if matrix[i - 1][j] > matrix[i][j] or (j - 1 >= 0 and matrix[i - 1][j - 1] > matrix[i][j]) or (j + 1 < m and matrix[i - 1][j + 1] > matrix[i][j]):
				output[i][j] = [0, max(matrix[i - 1][j], -1 if j - 1 < 0 else matrix[i - 1][j - 1], -1 if j + 1 >= m else matrix[i - 1][j + 1], output[i - 1][j][1], -1 if j - 1 < 0 else output[i - 1][j - 1][1], -1 if j + 1 >= m else output[i - 1][j + 1][1])]
			elif matrix[i][j] < output[i - 1][j][1] or (j - 1 >= 0 and matrix[i][j] < output[i - 1][j - 1][1]) or (j + 1 < m and matrix[i][j] < output[i - 1][j + 1][1]):
				output[i][j] = [0, max(output[i - 1][j][1], -1 if j - 1 < 0 else output[i - 1][j - 1][1], -1 if j + 1 >= m else output[i - 1][j + 1][1])]
	for i in range(n):
		for j in range(m):
			print(output[i][j][0], end='')
		print()


from collections import deque
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	z = [[] for i in range(n * m + 1)]
	a = []
	dc = [['.' for i in range(m)] for i in range(n)]
	vis = set([n * m])
	for i in range(n):
		a.append(list(map(int, input().split())))
		for j in range(m):
			z[a[i][j]] = [i, j]
	last = n * m
	while len(vis) != n * m:
		vis.add(last)
		dc[z[last][0]][z[last][1]] = '1'
		q = deque([[z[last][0], z[last][1]]])
		while q:
			f = q.popleft()
			if f[0] + 1 >= n:
				continue
			if f[1] - 1 >= 0:
				if dc[f[0] + 1][f[1] - 1] == '.':
					dc[f[0] + 1][f[1] - 1] = '0'
					vis.add(a[f[0] + 1][f[1] - 1])
					q.append([f[0] + 1, f[1] - 1])
			if f[1] + 1 <= m - 1:
				if dc[f[0] + 1][f[1] + 1] == '.':
					dc[f[0] + 1][f[1] + 1] = '0'
					vis.add(a[f[0] + 1][f[1] + 1])
					q.append([f[0] + 1, f[1] + 1])
			if dc[f[0] + 1][f[1]] == '.':
				dc[f[0] + 1][f[1]] = '0'
				vis.add(a[f[0] + 1][f[1]])
				q.append([f[0] + 1, f[1]])
		while last in vis:
			last -= 1
	for i in dc:
		print(''.join(i))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = []
	dirty = []
	for i in range(n):
		x = list(map(int, input().split()))
		y = [1 for i in range(m)]
		grid.append(x)
		dirty.append(y)
	for i in range(1, n):
		for j in range(m):
			if j > 0 and j < m - 1:
				if grid[i][j] < max(grid[i - 1][j - 1], grid[i - 1][j], grid[i - 1][j + 1]):
					grid[i][j] = max(grid[i - 1][j - 1], grid[i - 1][j], grid[i - 1][j + 1])
					dirty[i][j] = 0
			elif j == 0 and m == 1:
				if grid[i][j] < max(grid[i - 1][j]):
					grid[i][j] = max(grid[i - 1][j])
					dirty[i][j] = 0
			elif j == 0:
				if grid[i][j] < max(grid[i - 1][j], grid[i - 1][j + 1]):
					grid[i][j] = max(grid[i - 1][j], grid[i - 1][j + 1])
					dirty[i][j] = 0
			elif j == m - 1:
				if grid[i][j] < max(grid[i - 1][j - 1], grid[i - 1][j]):
					grid[i][j] = max(grid[i - 1][j - 1], grid[i - 1][j])
					dirty[i][j] = 0
	for i in dirty:
		for j in i:
			print(j, end='')
		print()


t = int(input())
for i in range(t):
	arr = []
	(n, m) = map(int, input().split())
	z = ['1' for i in range(m)]
	arr.append(list(map(int, input().split())))
	print(''.join(z))
	for i in range(1, n):
		x = ''
		arr.append(list(map(int, input().split())))
		if arr[i][0] > arr[i - 1][0] and arr[i][0] > arr[i - 1][1]:
			x += '1'
		else:
			x += '0'
		arr[i][0] = max(arr[i - 1][0], arr[i][0], arr[i - 1][1])
		for j in range(1, m - 1):
			if arr[i][j] > arr[i - 1][j] and arr[i][j] > arr[i - 1][j + 1] and (arr[i][j] > arr[i - 1][j - 1]):
				x += '1'
			else:
				x += '0'
			arr[i][j] = max(arr[i - 1][j], arr[i][j], arr[i - 1][j + 1], arr[i - 1][j - 1])
		if arr[i][m - 1] > arr[i - 1][m - 1] and arr[i][m - 1] > arr[i - 1][m - 2]:
			x += '1'
		else:
			x += '0'
		arr[i][m - 1] = max(arr[i - 1][m - 2], arr[i][m - 1], arr[i - 1][m - 1])
		print(x)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	turn = []
	for j in range(n):
		row = list(map(int, input().split()))
		turn.append(row)
	print('1' * m)
	for j in range(1, n):
		clean = [1] * m
		for k in range(m):
			a = max(turn[j - 1][max(k - 1, 0)], turn[j - 1][k], turn[j - 1][min(k + 1, m - 1)])
			if a > turn[j][k]:
				turn[j][k] = a
				clean[k] = 0
		print(*clean, sep='')


t = int(input())
while t:
	l = []
	ll = []
	(n, m) = map(int, input().split())
	for i in range(n):
		li = list(map(int, input().split()))
		l.append(li)
		ll.append(list(li))
	for i in range(n):
		for j in range(m):
			if i - 1 >= 0 and j - 1 >= 0:
				ll[i][j] = max(ll[i][j], ll[i - 1][j - 1])
			if i - 1 >= 0:
				ll[i][j] = max(ll[i][j], ll[i - 1][j])
			if i - 1 >= 0 and j + 1 < m:
				ll[i][j] = max(ll[i][j], ll[i - 1][j + 1])
			if l[i][j] < ll[i][j]:
				print(0, end='')
			else:
				print(1, end='')
		print()
	t -= 1


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	s = []
	for __ in range(m):
		s.append([int(i) for i in input().split()])
	c = [[1 for i in range(n)] for i in range(m)]
	for i in range(1, m):
		for j in range(n):
			if j > 0 and s[i][j] < s[i - 1][j - 1]:
				c[i][j] = 0
			if j > 0:
				s[i][j] = max(s[i][j], s[i - 1][j - 1])
			if s[i][j] < s[i - 1][j]:
				c[i][j] = 0
			s[i][j] = max(s[i][j], s[i - 1][j])
			if j < n - 1 and s[i][j] < s[i - 1][j + 1]:
				c[i][j] = 0
			if j < n - 1:
				s[i][j] = max(s[i][j], s[i - 1][j + 1])
	for row in c:
		print(*row, sep='')


for t in range(int(input())):
	(n, m) = map(int, input().split())
	prev = list(map(int, input().split()))
	print('1' * m)
	for i in range(1, n):
		s = ''
		a = list(map(int, input().split()))
		temp = []
		for j in range(m):
			item = prev[j]
			if j + 1 < m:
				item = max(item, prev[j + 1])
			if j - 1 >= 0:
				item = max(item, prev[j - 1])
			if a[j] > item:
				s += '1'
				item = a[j]
			else:
				s += '0'
			temp.append(item)
		print(s)
		prev = temp


for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	A = []
	B = [['0' for x in range(M)] for x in range(N)]
	for __ in range(N):
		A.append(input().split())
	D = {}
	for i in range(N):
		for j in range(M):
			D[int(A[i][j])] = (i, j)
	for k in range(1, N * M + 1):
		(i, j) = D[k]
		B[i][j] = '1'
		for p in range(i + 1, N):
			diff = p - i
			for q in range(j - diff, j + diff + 1):
				if q >= 0 and q < M:
					B[p][q] = '0'
	for i in B:
		for j in i:
			print(j, end='')
		print()


def printer(ls):
	for i in range(len(ls)):
		for j in range(len(ls[i])):
			print(ls[i][j], end='')
		print()

def lss(ls, N, M):
	tmp = ls[:]
	ans = [[0 for i in range(M)] for j in range(N)]
	for i in range(N):
		if i == 0:
			for j in range(M):
				ans[i][j] = 1
		else:
			for j in range(M):
				if j == 0:
					tmp2 = max(tmp[i - 1][j], tmp[i - 1][j + 1])
				elif j == M - 1:
					tmp2 = max(tmp[i - 1][j], tmp[i - 1][j - 1])
				else:
					tmp2 = max(tmp[i - 1][j], tmp[i - 1][j + 1], tmp[i - 1][j - 1])
				if ls[i][j] > tmp2:
					ans[i][j] = 1
				else:
					ans[i][j] = 0
				tmp[i][j] = max(tmp2, tmp[i][j])
	printer(ans)
for _ in range(int(input())):
	(N, M) = [int(i) for i in input().split()]
	ls = []
	for i in range(N):
		tmp = [int(i) for i in input().split()]
		ls.append(tmp)
	lss(ls, N, M)


T = int(input())
while T > 0:
	(N, M) = [int(x) for x in input().split()]
	arr = [[int(x) for x in input().split()] for y in range(N)]
	ans = [['1' for x in range(M)] for y in range(N)]
	for i in range(1, N):
		for j in range(M):
			m = max(arr[i][j], arr[i - 1][j])
			if j - 1 >= 0:
				m = max(m, arr[i - 1][j - 1])
			if j + 1 < M:
				m = max(m, arr[i - 1][j + 1])
			if arr[i][j] != m:
				ans[i][j] = '0'
			arr[i][j] = m
	for i in range(N):
		print(''.join(ans[i]))
	T -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	k = []
	for i in range(n):
		for j in range(m):
			k.append([l[i][j], i, j])
	k.sort()
	s = []
	for i in range(n):
		s.append([0] * m)
	for i in k:
		x = i[1]
		y = i[2]
		s[x][y] = 1
		c = 1
		for j in range(x + 1, n):
			s[j][y] = 0
			for b in range(y - 1, max(y - c - 1, -1), -1):
				s[j][b] = 0
			for b in range(y + 1, min(m, y + c + 1)):
				s[j][b] = 0
			c += 1
	for i in s:
		print(''.join(map(str, i)))


t = int(input())
for i in range(t):
	(x, y) = list(map(int, input().strip().split()))
	a = []
	for j in range(x):
		a.append(list(map(int, input().strip().split())))
	op = [[0] * y for j in range(x)]
	mdt = [[0] * y for j in range(x)]
	for j in range(1, x):
		for k in range(y):
			mdt[j][k] = max(mdt[j - 1][max(0, k - 1)], mdt[j - 1][k], mdt[j - 1][min(y - 1, k + 1)], a[j - 1][max(0, k - 1)], a[j - 1][k], a[j - 1][min(y - 1, k + 1)])
	for j in range(x):
		for k in range(y):
			if mdt[j][k] < a[j][k]:
				op[j][k] = 1
	for j in range(x):
		print(''.join(list(map(str, op[j]))))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print('1' * m)
	prev = tuple(map(int, input().split()))
	for i in range(1, n):
		s = ''
		now = tuple(map(int, input().split()))
		prev_ = []
		for j in range(m):
			temp = prev[j]
			if j + 1 < m and prev[j + 1] > temp:
				temp = prev[j + 1]
			if j > 0 and prev[j - 1] > temp:
				temp = prev[j - 1]
			if temp < now[j]:
				s += '1'
				temp = now[j]
			else:
				s += '0'
			prev_.append(temp)
		prev = prev_
		print(s)


from collections import defaultdict
from heapq import *
import itertools, math

def parse_integer_list():
	return [int(x) for x in input().split()]

def before_me(A, i, j, M):
	if M == 1:
		val = A[i][j] > A[i - 1][j]
		A[i][j] = max(A[i][j], A[i - 1][j])
		return val
	if j == 0:
		val = A[i][j] > max(A[i - 1][j], A[i - 1][j + 1])
		A[i][j] = max(A[i][j], A[i - 1][j], A[i - 1][j + 1])
		return val
	if j == M - 1:
		val = A[i][j] > max(A[i - 1][j], A[i - 1][j - 1])
		A[i][j] = max(A[i][j], A[i - 1][j], A[i - 1][j - 1])
		return val
	val = A[i][j] > max(A[i - 1][j], A[i - 1][j - 1], A[i - 1][j + 1])
	A[i][j] = max(A[i][j], A[i - 1][j], A[i - 1][j - 1], A[i - 1][j + 1])
	return val

def handle_input(A, N, M):
	B = []
	res = []
	res.append('1' * M)
	for i in range(1, N):
		res.append('')
		for j in range(M):
			res[-1] += '1' if before_me(A, i, j, M) else '0'
	for i in range(len(res)):
		print(res[i])
T = int(input())
for i in range(T):
	(N, M) = parse_integer_list()
	A = []
	for i in range(N):
		A.append(parse_integer_list())
	handle_input(A, N, M)


for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	A = []
	B = [['1' for x in range(M)] for x in range(N)]
	C = [['1' for x in range(M)] for x in range(N)]
	for __ in range(N):
		A.append(list(map(int, input().split())))
	B[0] = A[0].copy()
	for i in range(1, N):
		p = i - 1
		for j in range(0, M):
			B[i][j] = A[p][j]
			B[i][j] = max(B[i][j], A[i][j])
			if j >= 1:
				B[i][j] = max(B[i][j], B[p][j - 1])
			if j <= M - 2:
				B[i][j] = max(B[i][j], B[p][j + 1])
	C[0] = [1] * M
	for i in range(1, N):
		for j in range(0, M):
			if B[i][j] > A[i][j]:
				C[i][j] = 0
	for i in range(0, N):
		for j in range(0, M):
			print(C[i][j], end='')
		print()


def setmax(i, M, A, B):
	for j in range(M):
		B[i + 1][j] = max(B[i + 1][j], A[i][j], B[i][j])
		if j > 0:
			B[i + 1][j - 1] = max(B[i + 1][j - 1], A[i][j], B[i][j])
		if j < M - 1:
			B[i + 1][j + 1] = max(B[i + 1][j + 1], A[i][j], B[i][j])
T = int(input())
ans = []
for _ in range(T):
	(N, M) = [int(i) for i in input().split()]
	A = []
	for i in range(N):
		x = [int(i) for i in input().split()]
		A.append(x)
	B = [[0 for i in range(M)] for j in range(N)]
	for i in range(N - 1):
		setmax(i, M, A, B)
	for i in range(N):
		s = ''
		for j in range(M):
			if B[i][j] > A[i][j]:
				s += '0'
			else:
				s += '1'
		ans.append(s)
for i in ans:
	print(i)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for _ in range(n):
		matrix.append(list(map(int, input().split())))
	ans = [[-1] * m for _ in range(n)]
	di = ((1, -1), (1, 0), (1, 1))
	for i in range(n):
		for j in range(m):
			if ans[i][j] == -1:
				ans[i][j] = 1
			for d in di:
				(ii, jj) = (i + d[0], j + d[1])
				if ii >= n or jj >= m or ii < 0 or (jj < 0):
					continue
				if matrix[ii][jj] < matrix[i][j]:
					ans[ii][jj] = 0
					matrix[ii][jj] = matrix[i][j]
	for i in ans:
		print(''.join(map(str, i)))


for _ in range(int(input())):
	(ro, col) = map(int, input().split())
	grid = [[0] * (col + 2)]
	for i in range(ro):
		grid += [[0] + list(map(int, input().split())) + [0]]
	dp = [[0] * (col + 2) for i in range(ro + 1)]
	for i in range(1, ro + 1):
		for j in range(1, col + 1):
			dp[i][j] = max([grid[i - 1][j - 1], grid[i - 1][j], grid[i - 1][j + 1], dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]])
	ans = [['0'] * col for i in range(ro)]
	for i in range(ro):
		for j in range(col):
			if grid[i + 1][j + 1] > dp[i + 1][j + 1]:
				ans[i][j] = '1'
	for i in ans:
		print(''.join(i))


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = [int(s) for s in input().split()]
	l = [[-1 for i in range(m + 2)]] + [[-1] + [int(s) for s in input().split()] + [-1] for j in range(n)] + [[-1 for i in range(m + 2)]]
	l1 = [[0 for i in range(m + 2)] for j in range(n + 2)]
	for i in range(n + 2):
		for j in range(m + 2):
			l1[i][j] = l[i][j]
	dirtyw = defaultdict(lambda : 0)
	for i in range(2, n + 1):
		for j in range(1, m + 1):
			w = max(l1[i][j], l1[i - 1][j - 1], l1[i - 1][j], l1[i - 1][j + 1])
			l1[i][j] = w
	ans = set()
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			ans.add(l1[i][j])
	an = [[0 for i in range(m)] for j in range(n)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if l[i][j] in ans:
				an[i - 1][j - 1] = '1'
			else:
				an[i - 1][j - 1] = '0'
	for i in an:
		print(''.join(i))


for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	matrix = []
	for i in range(N):
		l = list(map(int, input().split()))
		matrix.append(l)
	for i in range(1, N):
		for j in range(M):
			if j == 0:
				if max(matrix[i - 1][j], matrix[i - 1][j + 1]) > matrix[i][j]:
					matrix[i][j] = max(matrix[i - 1][j], matrix[i - 1][j + 1])
			elif j == M - 1:
				if max(matrix[i - 1][j], matrix[i - 1][j - 1]) > matrix[i][j]:
					matrix[i][j] = max(matrix[i - 1][j], matrix[i - 1][j - 1])
			elif max(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i - 1][j + 1]) > matrix[i][j]:
				matrix[i][j] = max(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i - 1][j + 1])
	ans = [[1] * M for i in range(N)]
	for i in range(1, N):
		for j in range(M):
			if j == 0:
				if max(matrix[i - 1][j], matrix[i - 1][j + 1]) >= matrix[i][j]:
					ans[i][j] = 0
			elif j == M - 1:
				if max(matrix[i - 1][j], matrix[i - 1][j - 1]) >= matrix[i][j]:
					ans[i][j] = 0
			elif max(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i - 1][j + 1]) >= matrix[i][j]:
				ans[i][j] = 0
	for i in range(N):
		for j in range(M):
			print(ans[i][j], end='')
		print()


from sys import stdin, stdout
import sys
from bisect import bisect_left, bisect_right
t = int(stdin.readline().strip())
for _ in range(t):
	(n, m) = stdin.readline().strip().split(' ')
	(n, m) = (int(n), int(m))
	arr = []
	for i in range(n):
		arr.append(list(map(int, stdin.readline().strip().split(' '))))
	ctr = 0
	visited = [[False for i in range(m)] for j in range(n)]
	sol = [[1 for i in range(m)] for j in range(n)]
	pq = []
	for i in range(n):
		for j in range(m):
			pq.append((arr[i][j], i, j))
	pq = sorted(pq, key=lambda e: e[0], reverse=True)
	for i in pq:
		(cv, yo, xo) = i
		if visited[yo][xo]:
			continue
		else:
			stack = [xo, yo]
			while len(stack):
				y = stack.pop(-1)
				x = stack.pop(-1)
				visited[y][x] = True
				ctr += 1
				sol[y][x] = 0
				if x - 1 >= 0 and x - 1 < m and (y + 1 >= 0) and (y + 1 < n):
					if not visited[y + 1][x - 1]:
						stack.append(x - 1)
						stack.append(y + 1)
				if x >= 0 and x < m and (y + 1 >= 0) and (y + 1 < n):
					if not visited[y + 1][x]:
						stack.append(x)
						stack.append(y + 1)
				if x + 1 >= 0 and x + 1 < m and (y + 1 >= 0) and (y + 1 < n):
					if not visited[y + 1][x + 1]:
						stack.append(x + 1)
						stack.append(y + 1)
			sol[yo][xo] = 1
	for i in sol:
		for j in i:
			stdout.write(str(j))
		stdout.write('\n')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for j in range(n):
		arr += [[int(j) for j in input().split()]]
	dp = [[0 for i in range(m)] for j in range(n)]
	ans = [[0 for i in range(m)] for j in range(n)]
	for i in range(m):
		dp[0][i] = arr[0][i]
		ans[0][i] = 1
	if m == 1:
		for i in range(1, n):
			dp[i][0] = max(dp[i - 1][0], arr[i][0])
			if dp[i][0] == arr[i][0]:
				ans[i][0] = 1
		for x in ans:
			print(*x, sep='')
		continue
	for i in range(1, n):
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], arr[i][0])
		if dp[i][0] == arr[i][0]:
			ans[i][0] = 1
		for j in range(1, m - 1):
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1], arr[i][j])
			if dp[i][j] == arr[i][j]:
				ans[i][j] = 1
		dp[i][m - 1] = max(dp[i - 1][m - 1], dp[i - 1][m - 2], arr[i][m - 1])
		if dp[i][m - 1] == arr[i][m - 1]:
			ans[i][m - 1] = 1
	for x in ans:
		print(*x, sep='')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	aa = []
	it = []
	for i in range(n):
		itt = list(map(int, input().split()))
		it.append(itt[:])
	tt = [i[:] for i in it]
	for i in range(1, n):
		for j in range(m):
			if j == 0 and m == 1:
				tt[i][j] = max(tt[i][j], tt[i - 1][j])
			elif j == 0:
				tt[i][j] = max([tt[i][j], tt[i - 1][j], tt[i - 1][j + 1]])
			elif j == m - 1:
				tt[i][j] = max([tt[i][j], tt[i - 1][j], tt[i - 1][j - 1]])
			else:
				tt[i][j] = max([tt[i][j], tt[i - 1][j], tt[i - 1][j - 1], tt[i - 1][j + 1]])
	for i in range(n):
		for j in range(m):
			if it[i][j] == tt[i][j]:
				print('1', end='')
			else:
				print('0', end='')
		print()
	continue
	vis = [['0' for i in range(m)] for j in range(n)]
	for ii in aa:
		(x, y) = ii[1:]
		vis[x][y] = '1'
		(a, b) = (y, y)
		x -= 1
		while x >= 0:
			a = max(0, a - 1)
			b = min(m - 1, b + 1)
			for i in range(a, b + 1):
				vis[x][i] = '0'
			x -= 1
	for i in vis[-1::-1]:
		print(''.join(i))


def valid(i, j, n, m):
	if i < 0 or i >= n or j < 0 or (j >= m):
		return False
	return True
t = int(input())
for _ in range(t):
	(n, m) = input().strip().split()
	(n, m) = (int(n), int(m))
	arr = [0] * n
	for i in range(n):
		arr[i] = input().strip().split()
		for j in range(m):
			arr[i][j] = int(arr[i][j])
	dp = [0] * n
	for i in range(n):
		dp[i] = [0] * m
	for i in range(n):
		for j in range(m):
			dp[i][j] = arr[i][j]
			if valid(i - 1, j - 1, n, m):
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1])
			if valid(i - 1, j, n, m):
				dp[i][j] = max(dp[i][j], dp[i - 1][j])
			if valid(i - 1, j + 1, n, m):
				dp[i][j] = max(dp[i][j], dp[i - 1][j + 1])
	for i in range(n):
		for j in range(m):
			if arr[i][j] >= dp[i][j]:
				print(1, end='')
			else:
				print(0, end='')
		print()
	print()


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().strip().split()]
	mat = []
	clean = []
	for i in range(n):
		row = [int(x) for x in input().strip().split()]
		clean.append([0] * m)
		mat.append(row)
	clean[0] = [1] * m
	for i in range(1, n):
		for j in range(m):
			upleft = 0 if j - 1 < 0 else mat[i - 1][j - 1]
			upper = mat[i - 1][j]
			upright = 0 if j + 1 >= m else mat[i - 1][j + 1]
			if mat[i][j] > max(upleft, upper, upright):
				clean[i][j] = 1
			else:
				mat[i][j] = max(upleft, upper, upright)
	for i in range(n):
		print(*clean[i], sep='')


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	l = [[0 for i in range(M + 2)]]
	f = [[0 for i in range(M + 2)]]
	for i in range(N):
		X = [0] + list(map(int, input().split())) + [0]
		l.append(X[:])
		f.append(X[:])
	l.append([0 for i in range(M + 2)])
	f.append([0 for i in range(M + 2)])
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			x = max(l[i - 1][j - 1], l[i - 1][j], l[i - 1][j + 1])
			if l[i][j] > x:
				f[i][j] = 1
			else:
				f[i][j] = 0
				l[i][j] = x
	for i in f[1:-1]:
		for j in i[1:-1]:
			print(j, end='')
		print()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	get_ups = lambda r, c: [(r - 1, c + i) for i in [1, 0, -1] if 0 <= c + i < m]
	grid = [list(map(int, input().split())) for _ in range(n)]
	res = [[0] * m for _ in range(n)]
	res[0] = ['1'] * m
	for i in range(1, n):
		for j in range(m):
			t = 1
			for (r, c) in get_ups(i, j):
				if grid[r][c] > grid[i][j]:
					grid[i][j] = grid[r][c]
					t = 0
			res[i][j] = '1' if t else '0'
	for r in res:
		print(''.join(r))


from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10 ** 9 + 7
spf = [i for i in range(MAXN)]

def sieve():
	for i in range(2, MAXN, 2):
		spf[i] = 2
	for i in range(3, int(MAXN ** 0.5) + 1):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def fib(n, m):
	if n == 0:
		return [0, 1]
	else:
		(a, b) = fib(n1 // 2)
		c = a % m * (b % m * 2 - a % m) % m
		d = a % m * (a % m) % m + b % m * b % m % m
		if n % 2 == 0:
			return [c, d]
		else:
			return [d, c + d]

def charIN(x=' '):
	return sys.stdin.readline().strip().split(x)

def arrIN(x=' '):
	return list(map(int, sys.stdin.readline().strip().split(x)))

def ncr(n, r):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % MOD
		den = den * (i + 1) % MOD
	return num * pow(den, MOD - 2, MOD) % MOD

def flush():
	return sys.stdout.flush()
for _ in range(int(input())):
	(n, m) = arrIN()
	a = [arrIN() for i in range(n)]
	mx = [[0 for i in range(m + 2)] for j in range(n + 2)]
	for i in range(n):
		for j in range(m):
			mx[i][j] = max(a[i][j], mx[i - 1][j], mx[i - 1][j - 1], mx[i - 1][j + 1])
	for i in range(n):
		for j in range(m):
			print(1 if a[i][j] >= mx[i][j] else 0, end='')
		print()


tc = int(input())
for _ in range(tc):
	(n, m) = map(int, input().split())
	mt = []
	ans = []
	for __ in range(n):
		t = list(map(int, input().split()))
		mt.append(t)
	ans.append([1] * m)
	for i in range(1, n):
		temp = []
		for j in range(m):
			tl = 0 if j - 1 < 0 else mt[i - 1][j - 1]
			tp = mt[i - 1][j]
			tr = 0 if j + 1 >= m else mt[i - 1][j + 1]
			if mt[i][j] > max([tl, tp, tr]):
				temp.append(1)
			else:
				temp.append(0)
				mt[i][j] = max([tl, tp, tr])
		ans.append(temp)
	for i in ans:
		print(*i, sep='')


import io, sys, atexit, os
import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations

def li():
	return list(map(int, sys.stdin.readline().split()))

def num():
	return map(int, sys.stdin.readline().split())

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	gg = find_gcd(x, y)
	return x * y // gg
mm = 1000000007

def solve():
	t = nu()
	for tt in range(t):
		(n, m) = num()
		x = [0] * n
		a = [0] * n
		ss = []
		vis = [0] * n
		for i in range(n):
			vv = li()
			x[i] = vv
			a[i] = [1] * m
			vis[i] = [0] * m
			for j in range(m):
				ss.append((vv[j], i, j))
		ss.sort(reverse=True)
		for i in range(len(ss)):
			p = ss[i][1]
			q = ss[i][2]
			if vis[p][q] == 1:
				continue
			a[p][q] = 1
			vis[p][q] = 1
			zp = p + 1
			zo = q - 1
			while zp < n and zo >= 0:
				if vis[zp][zo] == 1:
					break
				for j in range(zp, n):
					if vis[j][zo] == 1:
						break
					a[j][zo] = 0
					vis[j][zo] = 1
				zp += 1
				zo -= 1
			zp = p + 1
			zo = q + 1
			while zp < n and zo < m:
				if vis[zp][zo] == 1:
					break
				for j in range(zp, n):
					if vis[j][zo] == 1:
						break
					a[j][zo] = 0
					vis[j][zo] = 1
				zp += 1
				zo += 1
			zp = p + 1
			zo = q
			for j in range(zp, n):
				if vis[j][zo] == 1:
					break
				a[j][zo] = 0
				vis[j][zo] = 1
		for i in range(n):
			print(*a[i], sep='')
solve()


import numpy as np
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = np.zeros((n + 2, m + 2), dtype=int)
	dp = np.zeros((n + 2, m + 2), dtype=int)
	for i in range(1, n + 1):
		t = list(map(int, input().split()))
		for j in range(1, m + 1):
			a[i][j] = t[j - 1]
			dp[i][j] = max(a[i][j], dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if a[i][j] == dp[i][j]:
				dp[i][j] = 1
			else:
				dp[i][j] = 0
			print(dp[i][j], end='')
		print()


t = int(input())
while t:
	t = t - 1
	(n, m) = map(int, input().split())
	arr = [0] * m
	arrm = []
	for i in range(n):
		arr1 = arr.copy()
		arrm.append(arr1)
	build = []
	for i in range(n):
		build.append(list(map(int, input().split())))
	for j in range(m):
		arrm[0][j] = build[0][j]
		if arrm[0][j] == build[0][j]:
			print('1', end='')
		else:
			print('0', end='')
	print()
	for i in range(1, n):
		for j in range(m):
			if j == 0:
				arrm[i][j] = max(max(build[i][j], arrm[i - 1][j]), arrm[i - 1][j + 1])
			elif j == m - 1:
				arrm[i][j] = max(max(build[i][j], arrm[i - 1][j]), arrm[i - 1][j - 1])
			else:
				arrm[i][j] = max(max(build[i][j], arrm[i - 1][j]), max(arrm[i - 1][j + 1], arrm[i - 1][j - 1]))
			if arrm[i][j] == build[i][j]:
				print('1', end='')
			else:
				print('0', end='')
		print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[0 for i in range(m + 2)]]
	for i in range(n):
		a.append([0] + list(map(int, input().split())) + [0])
	a.append([0 for i in range(m + 2)])
	ans = [[0 for i in range(m + 2)] for j in range(n + 2)]
	for j in range(1, m + 1):
		ans[1][j] = a[1][j]
	for i in range(2, n + 1):
		for j in range(1, m + 1):
			ans[i][j] = max(ans[i - 1][j], ans[i - 1][j + 1], ans[i - 1][j - 1], a[i - 1][j], a[i - 1][j + 1], a[i - 1][j - 1])
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if a[i][j] >= ans[i][j]:
				print(1, end='')
			else:
				print(0, end='')
		print()


R = lambda : map(int, input().split())
(t,) = R()
for _ in range(t):
	(n, m) = R()
	a = r = [0] * (m + 2)
	for _ in range(n):
		r = [max(r[i - 1:i + 2] + a[i - 1:i + 2]) for i in range(1, m + 1)]
		a = list(R())
		print(''.join(('10'[x > y] for (x, y) in zip(r, a))))
		r = [0] + r + [0]
		a = [0] + a + [0]