# your code goes here$a=0
$a=1
class Node
	attr_accessor :rank
	attr_accessor :children
	attr_accessor :parent
	
	def initialize
		@parent=nil
		@children=[]
	end
	
	def dup()
		result=Node.new
		result.rank=@rank
		@children.each{|c|
			x=c.dup()
			x.parent=result
			result.children<<x
		}
		return result
	end
	
	def leaf()
		return self if(children.length==0)
		return @children.last.leaf
	end
	
	def succ()
#		$a+=1
		l=leaf()
		p=l.parent
		return false if(p==nil)
		p.children.pop
		pp=p.parent
		if(pp!=nil)
		then
			$a.times{
				n=p.dup
				n.parent=pp
				pp.children<<n
			}
		else
			pp=p
		end
		
		if(l.rank>0)
		then
			n=generate($a,l.rank-1)
			n.parent=pp
			pp.children<<n
		end
		return true
	end

	def dump()
		lp_list=["(","[","<","{"]
		rp_list=[")","]",">","}"]
		if @rank>3
			lp="{"
			rp="}"
		else
			lp=lp_list[@rank]
			rp=rp_list[@rank]
		end
		return lp+children.collect{|c| c.dump()}.join()+rp
	end
end

def generate(i,rank)
	n=Node.new
	n.rank=rank
	return n if(i==0)
	c=generate(i-1,rank)
	c.parent=n
	n.children<<c
	return n
end

x=generate(1,3)
i=0
print x.dump,"\n"
while(x.succ)
	print x.dump,"\n"
	i+=1
	break if(i>100)
end