import random

def fixPartition(Ss, target):
	Ts = []
	for s in Ss:
		m = min(s)
		if m < 0:
			t = set(a - m for a in s) 
			target -= m
		else:
			t = s
		Ts.append(t)
	return (Ts, target)

def randomPartition(size, target):
	while True:
		X = set()
		Y = set()
		Z = set()
		while max(len(X), len(Y), len(Z)) < size:
			x = random.randint(0, target//3*2);
			y = random.randint(0, target//3*2);
			z = target - x - y
			X.add(x)
			Y.add(y)
			Z.add(z)

		A = None
		if len(X) < size:
			if len(Y) < size:
				if len(Z) < size:
					pass
				else:
					A = X
					B = Y
			else:
				if len(Z) < size:
					A = X
					B = Z
				else:
					B = X
		else:
			if len(Y) < size:
				if len(Z) < size:
					A = Y
					B = Z
				else:
					B = Y
			else:
				if len(Z) < size:
					B = Z
				else:
					continue

		if A != None:
			while len(A) < size:
				a = random.randint(0, target//3*2)
				A.add(a)
		
		while len(B) < size - 2:
			b = random.randint(0, target//4*3)
			B.add(b)
		m = size * target - sum(X) - sum(Y) - sum(Z)
		
		if len(B) == size - 2:
			for c in range(m//2, target*2):
				if c not in B and m - c not in B:
					B.add(c)
					B.add(m-c)

					yield fixPartition([X, Y, Z], target)
					break
		if len(B) == size - 1:
			if m not in B:
				B.add(m)
				yield fixPartition([X, Y, Z], target)
		continue
		
def hasMatching(X, Y, Z,target):
	if len(X) == 0:
		return True
	x = next(iter(X))
	for y in Y:
		z = target - x - y
		if z in Z:
			XX = X.copy(); XX.remove(x);
			YY = Y.copy(); YY.remove(y);
			ZZ = Z.copy(); ZZ.remove(z);
			if hasMatching(XX, YY, ZZ, target):
				return True
	return False

def specialInstance(X, Y, Z, target):
	XYZ = set()
	XYZ.update(X)
	XYZ.update(y + 3 * target for y in Y)	
	XYZ.update(z + 6 * target for z in Z)	
	return ([XYZ, XYZ, XYZ], 10*target)

def test(size, wanted):
	i = 0
	j = 0
	for [X, Y, Z], target in randomPartition(size, wanted):
		i += 1
		if hasMatching(X, Y, Z, target):
			continue
		j += 1
		[Xs, Ys, Zs], ts = specialInstance(X, Y, Z, target)	
		if hasMatching(Xs, Ys, Zs, ts):
			print(X, Y, Z, target)
			break
		print (i, j, i-j, ": ", X, Y, Z, target)

def main():
	pass