There is a matrix of size N \times M. Two distinct cells of the matrix (x_{1}, y_{1}) and (x_{2}, y_{2}) are painted with colors \text{1} and \text{2} respectively.

You have to paint the remaining cells of the matrix such that:
No two adjacent cells are painted in same color. 
Each color is an integer from 1 to 10^{9} (both inclusive).
The number of distinct colors used is minimum (including \text{1} and \text{2}). 

Note: 
1. You cannot repaint the cells (x_{1}, y_{1}) and (x_{2}, y_{2}).
2. Two cells are adjacent if they share a common edge. Thus, for a cell (x,y) there are 4 adjacent cells. The adjacent cells are (x, y+1), (x, y-1), (x+1,y), and (x-1,y).

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow. Each test case consists of 3 lines.
- The first line contains two space seperated integers N and M denoting the dimensions of the matrix.
- The second line contains two integers x_{1} and y_{1}, denoting the coordinates of cell which is painted \text{1}.
- The third line contains two integers x_{2} and y_{2}, denoting the coordinates of cell which is painted \text{2}.

------ Output Format ------ 

For each test case, output N lines, each consisting of M space separated integers where j^{th} integer in i^{th} line denotes the color of cell in i^{th} row and j^{th} column of the matrix and must be in [1, 10^{9}] inclusive.

In case of multiple possible answers, output any.

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

$1 ≤ T ≤ 100$
$2 ≤ N, M ≤ 10^{5}$
$1 ≤ x_{1}, x_{2} ≤ N$
$1 ≤ y_{1}, y_{2} ≤ M$
$(x_{1}, y_{1}) \neq (x_{2}, y_{2})$
- Sum of $N \cdot M$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
2
2 2
1 1
2 2
2 3
1 1
1 2

----- Sample Output 1 ------ 
1 4
4 2
1 2 1
2 1 2

----- explanation 1 ------ 
Test Case $1$:  
  
The initially painted cells are $(1,1)$ and $(2,2)$. One possible way is to paint the remaining cells with color $4$. This way, no two adjacent cells have the same color.  
Note that, instead of color $4$, we can use any other color in the range $[1, 10^{9}]$ except colors $1$ and $2$.  
The number of distinct colors used in this case is $3$. It can be shown that the minimum number of distinct colors cannot be less than $3$.

Test Case $2$:  
  
The initially painted cells are $(1,1)$ and $(1,2)$. One possible way is to paint the remaining cells as shown in the figure. This way, no two adjacent cells have the same color.  
The number of distinct colors used in this case is $2$. It can be shown that the minimum number of distinct colors cannot be less than $2$.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	(c, d) = map(int, input().split())
	c -= 1
	d -= 1
	mat = [[4] * m for i in range(n)]
	mat[a][b] = 1
	mat[c][d] = 2
	for i in range(n):
		for j in range(m):
			if i == a and j == b or (i == c and j == d):
				continue
			elif (i + j) % 2 == (a + b) % 2:
				mat[i][j] = 1
			elif (i + j) % 2 == (c + d) % 2:
				mat[i][j] = 2
	for i in mat:
		print(*i)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	(n, m) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	mat = [[0] * m for i in range(n)]
	if (x1 + y1) % 2 == (x2 + y2) % 2:
		if (x1 + y1) % 2 == 0:
			start = 1
			other = 4
		else:
			start = 4
			other = 1
		for i in range(n):
			for j in range(m):
				if i + 1 == x2 and j + 1 == y2:
					mat[i][j] = 2
				elif (i + j) % 2 == 0:
					mat[i][j] = start
				else:
					mat[i][j] = other
	else:
		if (x1 + y1) % 2 == 0:
			start = 1
			other = 2
		else:
			start = 2
			other = 1
		for i in range(n):
			for j in range(m):
				if (i + j + 2) % 2 == 0:
					mat[i][j] = start
				else:
					mat[i][j] = other
	for i in mat:
		print(*i)
t = int(input())
while t != 0:
	solve()
	t -= 1


import math
import os
import random
import re
import sys
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	A = (x1 + y1) % 2
	B = (x2 + y2) % 2
	if A == B:
		for j in range(N):
			for k in range(M):
				if j == x1 - 1 and k == y1 - 1:
					print(1, end=' ')
				elif j == x2 - 1 and k == y2 - 1:
					print(2, end=' ')
				elif (j + k) % 2 == A:
					print(1, end=' ')
				else:
					print(4, end=' ')
			print()
	else:
		for j in range(N):
			for k in range(M):
				if (j + k) % 2 == A:
					print(1, end=' ')
				else:
					print(2, end=' ')
			print()


def parity(x, y):
	if (x + y) % 2 == 0:
		return True
	else:
		return False
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	if parity(x1, y1) == parity(x2, y2):
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if parity(i, j) == parity(x1, y1):
					if i == x2 and j == y2:
						print(2, end=' ')
					else:
						print(1, end=' ')
				else:
					print(4, end=' ')
			print()
	else:
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if parity(i, j) == parity(x1, y1):
					print(1, end=' ')
				else:
					print(2, end=' ')
			print()


tc = int(input())
for i in range(tc):
	(n, m) = list(map(int, input().split()))
	(x1, y1) = list(map(int, input().split()))
	(x2, y2) = list(map(int, input().split()))
	if (abs(x1 - x2) + abs(y1 - y2)) % 2 == 0:
		color2 = 4
	else:
		color2 = 2
	if (x1 + y1) % 2 == 0:
		color1 = 1
	else:
		color1 = color2
		color2 = 1
	for j in range(n):
		for k in range(m):
			sepat = ' '
			if k == m - 1:
				sepat = '\n'
			if j + 1 == x2 and k + 1 == y2:
				print(2, end=sepat)
			elif (j + k) % 2 == 0:
				print(color1, end=sepat)
			else:
				print(color2, end=sepat)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	inc = 0 if (x1 + y1) % 2 == 0 else 1
	if (x1 + y1) % 2 != (x2 + y2) % 2:
		for i in range(inc, n + inc):
			if i % 2 == 0:
				print('1 2 ' * (m // 2), '1' * (m % 2), sep='')
			else:
				print('2 1 ' * (m // 2), '2' * (m % 2), sep='')
	else:
		l = []
		for i in range(inc, n + inc):
			if i % 2 == 0:
				l.append([1, 2] * (m // 2) + [1] * (m % 2))
			else:
				l.append([2, 1] * (m // 2) + [2] * (m % 2))
		l[x2 - 1][y2 - 1] = 2
		if x2 != n:
			l[x2][y2 - 1] = 4
		if x2 != 1:
			l[x2 - 2][y2 - 1] = 4
		if y2 != 1:
			l[x2 - 1][y2 - 2] = 4
		if y2 != m:
			l[x2 - 1][y2] = 4
		for i in l:
			print(*i)


T = int(input())
while T:
	T -= 1
	(N, M) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x1, y1) = (x1 - 1, y1 - 1)
	(x2, y2) = (x2 - 1, y2 - 1)
	if x1 + y1 & 1 != x2 + y2 & 1:
		for i in range(N):
			for j in range(M):
				if i + j & 1 == x1 + y1 & 1:
					print(1, end=' ')
				else:
					print(2, end=' ')
			print()
	else:
		matrix = [[0] * M for _ in range(N)]
		for i in range(N):
			for j in range(M):
				if i + j & 1 == x1 + y1 & 1:
					matrix[i][j] = 1
				else:
					matrix[i][j] = 2
		matrix[x1][y1] = 1
		matrix[x2][y2] = 2
		if x2 > 0:
			matrix[x2 - 1][y2] = 4
		if x2 < N - 1:
			matrix[x2 + 1][y2] = 4
		if y2 > 0:
			matrix[x2][y2 - 1] = 4
		if y2 < M - 1:
			matrix[x2][y2 + 1] = 4
		for i in range(N):
			for j in range(M):
				print(matrix[i][j], end=' ')
			print()


from collections import deque
a = int(input())
for i in range(a):
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	z = list(map(int, input().split()))
	matrix = []
	for i in range(x[0]):
		matrix.append([])
		for j in range(x[1]):
			matrix[i].append(-1)
	matrix[y[0] - 1][y[1] - 1] = 1
	matrix[z[0] - 1][z[1] - 1] = 2
	adj = [[1, 0], [-1, 0], [0, -1], [0, 1]]
	queue = deque([])
	queue.append([y[0] - 1, y[1] - 1])
	while len(queue) != 0:
		curr = queue.popleft()
		for neigh in adj:
			dx = curr[0] + neigh[0]
			dy = curr[1] + neigh[1]
			if dx >= 0 and dx < x[0] and (dy >= 0) and (dy < x[1]):
				if matrix[dx][dy] == -1:
					queue.append([dx, dy])
					if matrix[curr[0]][curr[1]] == 1:
						matrix[dx][dy] = 2
					else:
						matrix[dx][dy] = 1
	curr = [z[0] - 1, z[1] - 1]
	for neigh in adj:
		dx = curr[0] + neigh[0]
		dy = curr[1] + neigh[1]
		if dx >= 0 and dx < x[0] and (dy >= 0) and (dy < x[1]):
			if matrix[dx][dy] == 2:
				matrix[dx][dy] = 4
	for rows in matrix:
		print(*rows)


from numpy import *
for i in range(int(input())):
	(x, y) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	l = ones((x, y), dtype=int)
	m = x2 - x1 + (y2 - y1)
	n = x1 + y1
	if m % 2 == 0:
		if n % 2 == 0:
			for i in range(x):
				for j in range(y):
					if (i + j) % 2 != 0:
						l[i][j] = 4
		else:
			for i in range(x):
				for j in range(y):
					if (i + j) % 2 == 0:
						l[i][j] = 4
	elif n % 2 == 0:
		for i in range(x):
			for j in range(y):
				if (i + j) % 2 != 0:
					l[i][j] = 2
	else:
		for i in range(x):
			for j in range(y):
				if (i + j) % 2 == 0:
					l[i][j] = 2
	l[x2 - 1][y2 - 1] = 2
	for i in l:
		for j in i:
			print(j, end=' ')
		print('')


def solve():
	(n, m) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	x1 -= 1
	x2 -= 1
	y1 -= 1
	y2 -= 1
	if (x1 + y1) % 2 != (x2 + y2) % 2:
		for i in range(n):
			for j in range(m):
				temp = (i + j) % 2
				if temp == (x1 + y1) % 2:
					print(1, end=' ')
				else:
					print(2, end=' ')
			print()
		return
	res = [[0] * m for i in range(n)]
	for i in range(n):
		for j in range(m):
			temp = (i + j) % 2
			if temp == (x1 + y1) % 2:
				res[i][j] = 1
			else:
				res[i][j] = 2
	res[x1][y1] = 1
	res[x2][y2] = 2
	if x2 > 0:
		res[x2 - 1][y2] = 4
	if x2 < n - 1:
		res[x2 + 1][y2] = 4
	if y2 > 0:
		res[x2][y2 - 1] = 4
	if y2 < m - 1:
		res[x2][y2 + 1] = 4
	for i in range(n):
		print(*res[i])
t = int(input())
for _ in range(t):
	solve()