# based god Donald Knuth

# http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

# sám bych to asi nevymyslel

class Cell:

	def __init__(self,left=None,right=None,up=None,down=None,col=None):

		self.left=left

		self.right=right

		self.up=up

		self.down=down

		self.col=col

class Column(Cell):

	def __init__(self,name,*args,**kwargs):

		super().__init__(*args,**kwargs)

		self.name=name

		self.size=0

	def cover(self):

		self.right.left=self.left

		self.left.right=self.right

		r=self.down

		while r is not self:

			c=r.right

			while c is not r:

				c.down.up=c.up

				c.up.down=c.down

				c.col.size-=1

				c=c.right

			r=r.down

	def uncover(self):

		r=self.up

		while r is not self:

			c=r.left

			while c is not r:

				c.col.size+=1

				c.down.up=c

				c.up.down=c

				c=c.left

			r=r.up

		self.right.left=self

		self.left.right=self

class Header:

	def __init__(self,left=None,right=None):

		self.left=left

		self.right=right

		self._res=[]

	def search(self,k=0):

		if self.right is self:

			self.print()

			return True

		if len(self._res)<=k:

			self._res.append(None)

		col=self.chooseCol()

		col.cover()

		row=col.down

		while row is not col:

			row=row.down

			self._res[k]=row

			c=row.right

			while c is not row:

				c.col.cover()

				self.search(k+1)

				c=row.right

			c=row.left

			while c is not row:

				c.col.uncover()

				c=c.left

		col.uncover()

	def chooseCol(self):

		c=self.right

		best=c.size

		res=c

		while c is not self:

			if c.size<best:

				best=c.size

				res=c

			c=c.right

		return res

	def print(self):

		for r in self._res:

			c=r.right

			while c is not r:

				print(c.col.name,end=" ")

				c=c.right

			print()

		print()

					res.append(((point,v), partialRes))