Chef has decided to start a new software company, the company's building has N offices numbered from 0 to N-1 and there's a computer in each office.

All offices' computers should be connected within a single network, so it's required to buy some ethernet cables and hubs. a cable connecting i-th office with j-th office has cost C_{i,j} also if the i-th office is connected with j other offices then it's required to buy a hub with capacity j and this will cost H_{i,j}, note that even if the hub with higher capacity is cheaper than the hub with capacity j the company will still buy the hub with capacity j. Each office should have exactly one hub.

Find a way for building the network so that all offices are connected to each other directly or indirectly while minimizing the total cost, it's not allowed to connect same pair of offices with more than one cable and it's not allowed to connect an office with itself.

Your solution is not required to find the most optimal solution. However, the less cost your solution will provide the more points you will get.

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

Since the input is large you will not be given it directly. Instead, you will be given some parameters and the generator used to generate the input.

The first line contains a single integer T denoting the number of test-cases

The first line of each test-case contains the integers N, C_{max}, H_{max}

The following 2*N lines, each contain two integers Seed_{i,1}, Seed_{i,2} the seeds required for generating the input.

Using one of the generators, C++ generator, java generator, python 2 generator you will get C and H arrays.

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

For each test-case output N lines, each line contains a string of N characters. if you want to connect i-th office and j-th office with a cable then i-th character of j-th line and  j-th character of i-th line both should be '1' otherwise they should be '0'. Note that i-th character of i-th line should always be '0' because you can't connect an office with itself.

Note that cables information is enough to uniquely determine what hub should be bought for each office.

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

$T = 5$
$N = 1000$
$0 ≤ C_{i,j} ≤ 1,000,000$
$0 ≤ H_{i,j} ≤ 1,000,000$
$ C_{i,j} = C_{j,i}$
$ C_{i,i} = 0$
$0 < Seed_{i,1}, Seed_{i,2} < 10^{18}$

------ Test Generation ------ 

There will be 10 test-files.

The cost of a cable is chosen uniformly at random between 0 and C_{max} and the cost of a hub is chosen uniformly at random between 0 and H_{max}.

In each of the 10 test-files there are 5 test-cases, the values of C_{max} and H_{max} are:

$First test-case: C_{max} = 40,000 and H_{max} = 1,000,000$
$Second test-case: C_{max} = 100,000 and H_{max} = 1,000,000$
$Third test-case: C_{max} = 200,000 and H_{max} = 1,000,000$
$Fourth test-case: C_{max} = 500,000 and H_{max} = 1,000,000$
$Fifth test-case: C_{max} = 1,000,000 and H_{max} = 1,000,000$

All seeds in input are randomly generated.

------ Scoring ------ 

You will receive a WA if you didn't follow output format or there is a pair of offices which are not connected.

Your score in a single test-case is equal to the cost of the network outputed in that test-case, your overall score is the sum of scores of all test-cases in all test-files.

During contest you will be able to get your score on first 2 test-files. After contest there will be rejudge on full tests set.

------ Example ------ 

Input:
1
4 10 20
123456789012 4567890123456
11111111111111 2222222222222
101010101010 2323232323232
112358132134 1928374655647
999999555555 5555559999999
234123124155 1241352352345
234213515123 1231245551223
523432523332 1234124515123

Output:
0111
1000
1000
1000

------ Explanation ------ 

Example case 1. note that the example doesn't follow constraints on T and N and also seeds are set by hand in this sample.

In this example we have the array C:

0 0 7 6
0 0 2 7
7 2 0 7
6 7 7 0

and the array H

9 10 2 0
7 9 0 7
9 3 15 18
10 3 20 5

In the output, first office is connected all other offices and that will make the cost of the network equal to S = 0 + 7 + 6 + 0 + 9 + 3 + 3 = 28, so the score on this test-case is 28.

Difficulty: VERY_HARD

Starter code:

Solutions:
import math
s = []

def xorshift128plus():
	global s
	(x, y) = s
	x ^= x << 23 & 2 ** 64 - 1
	s[0] = y
	s[1] = x ^ y ^ x >> 17 ^ y >> 26
	return y

def main():
	global s
	T = int(input())
	for t in range(T):
		(n, Cmax, Hmax) = map(int, input().split())
		C = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(i + 1, n):
				C[i][j] = C[j][i] = xorshift128plus() % (Cmax + 1)
		H = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(n):
				H[i][j] = xorshift128plus() % (Hmax + 1)
		for i in range(n):
			C[i][i] = math.inf
		N = [[0] * n for x in range(n)]
		for i in range(1, n):
			N[0][i] = 1
			N[i][0] = 1
		for i in range(n):
			for j in range(n):
				print(N[i][j], end='')
			print()
main()


s = []

def xorshift128plus():
	global s
	(x, y) = s
	x ^= x << 23 & 2 ** 64 - 1
	s[0] = y
	s[1] = x ^ y ^ x >> 17 ^ y >> 26
	return y

def main():
	global s
	t = int(input())
	while t > 0:
		t -= 1
		(n, cmax, hmax) = map(int, input().strip().split())
		c = [[0] * n for x in range(n)]
		h = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().strip().split()))
			for j in range(i + 1, n):
				c[i][j] = c[j][i] = xorshift128plus() % (cmax + 1)
		for i in range(n):
			s = list(map(int, input().strip().split()))
			for j in range(n):
				h[i][j] = xorshift128plus() % (hmax + 1)
		ans = [[0] * n for x in range(n)]
		for i in range(1, n):
			ans[i][0] = 1
			ans[0][i] = 1
		for i in range(n):
			for j in range(n):
				print(ans[i][j], end='')
			print(end='\n')
main()


s = []

def xorshift128plus():
	global s
	(x, y) = s
	x ^= x << 23 & 2 ** 64 - 1
	s[0] = y
	s[1] = x ^ y ^ x >> 17 ^ y >> 26
	return y

def main():
	global s
	T = int(input())
	for t in range(T):
		(n, Cmax, Hmax) = map(int, input().split())
		C = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(i + 1, n):
				C[i][j] = C[j][i] = xorshift128plus() % (Cmax + 1)
		H = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(n):
				H[i][j] = xorshift128plus() % (Hmax + 1)
		print('0' + '1' * (n - 1))
		for k in range(n - 1):
			print('1' + '0' * (n - 1))
main()


s = []

def xorshift128plus():
	global s
	(x, y) = s
	x ^= x << 23 & 2 ** 64 - 1
	s[0] = y
	s[1] = x ^ y ^ x >> 17 ^ y >> 26
	return y

def main():
	global s
	T = int(input())
	for t in range(T):
		(n, Cmax, Hmax) = map(int, input().split())
		C = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(i + 1, n):
				C[i][j] = C[j][i] = xorshift128plus() % (Cmax + 1)
		H = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(n):
				H[i][j] = xorshift128plus() % (Hmax + 1)
		for i in range(n):
			l = [1 for h in range(n)]
			if i == 0:
				l[0] = 0
			else:
				l = [0 for h in range(n)]
				l[0] = 1
			s = ''
			for j in range(n):
				s += str(l[j])
			print(s)
main()


import sys
from random import randint

class UnionFind:

	def __init__(self, n):
		self._id = list(range(n))
		self._sz = [1] * n

	def _root(self, i):
		j = i
		while j != self._id[j]:
			self._id[j] = self._id[self._id[j]]
			j = self._id[j]
		return j

	def find(self, p, q):
		return self._root(p) == self._root(q)

	def union(self, p, q):
		i = self._root(p)
		j = self._root(q)
		if self._sz[i] < self._sz[j]:
			self._id[i] = j
			self._sz[j] += self._sz[i]
		else:
			self._id[j] = i
			self._sz[i] += self._sz[j]
s = []

def xorshift128plus():
	global s
	(x, y) = s
	x ^= x << 23 & 2 ** 64 - 1
	s[0] = y
	s[1] = x ^ y ^ x >> 17 ^ y >> 26
	return y

def printCables(cables):
	for cable in cables:
		for ch in cable:
			print(ch, end='')
		print()

def printCables1(mst):
	for i in range(n):
		for j in range(n):
			if (i, j) in mst:
				print(1, end='')
			else:
				print(0, end='')
		print()

def Star():
	cables = []
	ind = getMinCenter()
	cables = genStar(ind)
	cables = addEdges(cables)
	cables = addEdges(cables)
	cables = addEdges(cables)
	cables = addEdges(cables)
	printCables(cables)

def doit():
	cables = []
	global n
	curRes = 10000000000
	limit = 1
	for ind in range(min(n, limit)):
		num = randint(0, n - 1)
		curCables = genStar(num)
		nextRes = calcPrice(curCables)
		if nextRes < curRes:
			curRes = nextRes
			cables = curCables
	printCables(cables)

def genStar(center):
	global amounts, n
	cables = []
	amounts = [0] * n
	for ind in range(n):
		if ind == center:
			s = ['1'] * n
			s[ind] = '0'
			amounts[ind] = n - 1
		else:
			s = ['0'] * n
			s[center] = '1'
			amounts[ind] = 1
		cables.append(s)
	return cables

def calcPrice(cables):
	global C, H
	res = 0
	hubs = 0
	cabs = 0
	for i in range(n):
		hub = 0
		cab = 0
		for j in range(n):
			if cables[i][j] == '1':
				hub += 1
				cab += C[i][j]
		cabs += cab
		hubs += H[i][hub]
	return cabs // 2 + hubs

def getMinCenter():
	global H
	cur = 1000000000
	curInd = -1
	for ind in range(n):
		if H[ind][-1] < cur:
			cur = H[ind][-1]
			curInd = ind
	return curInd

def MST():
	global C, edges, amounts
	edges = []
	amounts = [0] * n
	edges = createEdges()
	cables = [['0'] * n for x in range(n)]
	nodes = set([])
	mst = set([])
	uf = UnionFind(n)
	for edge in edges:
		(w, node1, node2) = edge
		if node1 == node2:
			continue
		if uf.find(node1, node2):
			continue
		uf.union(node1, node2)
		cables[node1][node2] = '1'
		cables[node2][node1] = '1'
		amounts[node1] += 1
		amounts[node2] += 1
	cables = addEdges(cables)
	cables = addEdges(cables)
	cables = addEdges(cables)
	cables = addEdges(cables)
	printCables(cables)

def Path():
	global C, edges, amounts
	edges = []
	amounts = [0] * n
	edges = createEdges()
	cables = [['0'] * n for x in range(n)]
	nodes = set([])
	mst = set([])
	total = 0
	for edge in edges:
		(w, node1, node2) = edge
		if node1 == node2:
			continue
		if amounts[node1] > 1:
			continue
		if amounts[node2] > 1:
			continue
		cables[node1][node2] = '1'
		cables[node2][node1] = '1'
		amounts[node1] += 1
		amounts[node2] += 1
		total += 1
		if total == n - 1:
			break
	cables = addEdges(cables)
	cables = addEdges(cables)
	cables = addEdges(cables)
	cables = addEdges(cables)
	printCables(cables)

def addEdges(cables):
	global edges, amounts
	for edge in edges:
		(w, node1, node2) = edge
		if cables[node1][node2] == '1':
			continue
		delta = C[node1][node2] - H[node1][amounts[node1]] - H[node2][amounts[node2]]
		delta += H[node1][amounts[node1] + 1] + H[node2][amounts[node2] + 1]
		if delta < 0:
			cables[node1][node2] = '1'
			cables[node2][node1] = '1'
			amounts[node1] += 1
			amounts[node2] += 1
	return cables

def createEdges():
	global C
	edges = []
	for i in range(n):
		for j in range(i + 1, n):
			edges.append((C[i][j], i, j))
	edges.sort()
	return edges

def main():
	global s, n, C, H, edges
	T = int(input())
	for t in range(T):
		(n, Cmax, Hmax) = map(int, input().split())
		C = [[0] * n for x in range(n)]
		edges = []
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(i + 1, n):
				C[i][j] = C[j][i] = xorshift128plus() % (Cmax + 1)
		H = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(n):
				H[i][j] = xorshift128plus() % (Hmax + 1)
		Star()
main()


import sys
from random import randint
s = []

def xorshift128plus():
	global s
	(x, y) = s
	x ^= x << 23 & 2 ** 64 - 1
	s[0] = y
	s[1] = x ^ y ^ x >> 17 ^ y >> 26
	return y

def printCables(cables):
	for cable in cables:
		for ch in cable:
			print(ch, end='')
		print()

def printCables1(mst):
	for i in range(n):
		for j in range(n):
			if (i, j) in mst:
				print(1, end='')
			else:
				print(0, end='')
		print()

def doit():
	cables = []
	global n
	curRes = 10000000000
	limit = 20
	for ind in range(min(n, limit)):
		num = randint(0, n - 1)
		curCables = genStar(num)
		nextRes = calcPrice(curCables)
		if nextRes < curRes:
			curRes = nextRes
			cables = curCables
	printCables(cables)

def genStar(center):
	cables = []
	for ind in range(n):
		if ind == center:
			s = ['1'] * n
			s[ind] = '0'
		else:
			s = ['0'] * n
			s[center] = '1'
		cables.append(s)
	return cables

def calcPrice(cables):
	global C, H
	res = 0
	hubs = 0
	cabs = 0
	for i in range(n):
		hub = 0
		cab = 0
		for j in range(n):
			if cables[i][j] == '1':
				hub += 1
				cab += C[i][j]
		cabs += cab
		hubs += H[i][hub]
	return cabs // 2 + hubs

def MST():
	global C, edges
	edges = createEdges()
	print(edges)
	cables = [[0] * n for x in range(n)]
	nodes = set([])
	mst = set([])
	for edge in edges:
		(w, node1, node2) = edge
		if node1 in nodes and node2 in nodes:
			continue
		cables[node1][node2] = 1
		cables[node2][node1] = 1
		nodes.add(node1)
		nodes.add(node2)
	printCables(cables)

def createEdges():
	global C
	edges = []
	for i in range(n):
		for j in range(i + 1, n):
			edges.append((C[i][j], i, j))
	edges.sort()
	return edges

def main():
	global s, n, C, H, edges
	edges = []
	T = int(input())
	for t in range(T):
		(n, Cmax, Hmax) = map(int, input().split())
		C = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(i + 1, n):
				C[i][j] = C[j][i] = xorshift128plus() % (Cmax + 1)
		H = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(n):
				H[i][j] = xorshift128plus() % (Hmax + 1)
		doit()
main()


import sys
s = []

def xorshift128plus():
	global s
	(x, y) = s
	x ^= x << 23 & 2 ** 64 - 1
	s[0] = y
	s[1] = x ^ y ^ x >> 17 ^ y >> 26
	return y

def printCables(cables):
	for cable in cables:
		for ch in cable:
			print(ch, end='')
		print()

def doit():
	cables = []
	global n
	curRes = 10000000000
	limit = 10
	for ind in range(min(n, limit)):
		curCables = genStar(ind)
		nextRes = calcPrice(curCables)
		if nextRes < curRes:
			curRes = nextRes
			cables = curCables
	printCables(cables)

def genStar(center):
	cables = []
	for ind in range(n):
		if ind == center:
			s = ['1'] * n
			s[ind] = '0'
		else:
			s = ['0'] * n
			s[center] = '1'
		cables.append(s)
	return cables

def calcPrice(cables):
	global C, H
	res = 0
	hubs = 0
	cabs = 0
	for i in range(n):
		hub = 0
		cab = 0
		for j in range(n):
			if cables[i][j] == '1':
				hub += 1
				cab += C[i][j]
		cabs += cab
		hubs += H[i][hub]
	return cabs // 2 + hubs

def main():
	global s, n, C, H
	T = int(input())
	for t in range(T):
		(n, Cmax, Hmax) = map(int, input().split())
		C = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(i + 1, n):
				C[i][j] = C[j][i] = xorshift128plus() % (Cmax + 1)
		H = [[0] * n for x in range(n)]
		for i in range(n):
			s = list(map(int, input().split()))
			for j in range(n):
				H[i][j] = xorshift128plus() % (Hmax + 1)
		doit()
main()