# 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()