#! /usr/bin/python


class hanoi:
        def __init__(self,ringsU,dU,sU,tU):

		self.rings = int(ringsU)
		# questi parametri non servono tanto
		self.s = sU #sorgente
		self.d = dU #destinazione
		self.t = tU #transizione
		self.move=0

		self.a=[]
		self.b=[]
		self.c=[]
		for i in range(0,self.rings):
			self.a.append(i+1)
#			self.b.append([])
#			self.c.append([])
		


	def hanoi(self,rings,d,s,t):
		if (rings > 0):
			self.hanoi(rings-1,t,s,d)
			self.muovi(s,d)
#			print "\nSiamo alla mossa "+str(self.move)+"\n"
			self.hanoi(rings-1,d,t,s)
	
	def muovi(self,s,d):
		self.move=self.move+1
		print "\nmuovo da "+ s +" a "+d

		#ecco in riassunto quello che faro' nelle prossime righe
		#
		#  1) 
		#copio il primo anello della torre sorgente nella torre destinazione
		#	
		#	
		#            S                    D
		#              |                     |
		#              |                     | 
		#              |                     | 
		#            [===] ------------->    |
		#          [=======]                 |
		#         [=========]             [=====]
		#      ----------------------------------------
		#	
		#	
		#  2)	 e cancello il suddetto anello

				
		#1)	
		
		if s=="a":
			anello_da_prendere=self.a[len(self.a)-1]
		else: 
			if s=="b":
				anello_da_prendere=self.b[len(self.b)-1]
			else:
				if s=="c":
					anello_da_prendere=self.c[len(self.c)-1]
	
		# usero' i dizionari come uno statement switch case????	
#		anello_s={"a":self.a[len(self.a)-1],"b":self.b[len(self.b)-1],"c":self.c[len(self.c)-1]}
		
#		anello_da_prendere=anello_s[s]
		
		print anello_da_prendere	

		if d=="a":
			self.a.append(anello_da_prendere)
		else: 
			if d=="b":
				self.b.append(anello_da_prendere)
			else: 
				if d=="c":
					self.c.append(anello_da_prendere)
		
#		anello_d={"a":self.a.append(anello_da_prendere),"b":self.b.append(anello_da_prendere),"c":self.c.append(anello_da_prendere)}


#		anello_d[d]
		
		#2)
		if s=="a":
			del self.a[len(self.a)-1]
		else: 
			if s=="b":
				del self.b[len(self.b)-1]
			else: 
				if s=="c":
					del self.c[len(self.c)-1]
	
#		cancella_anello={"a":del self.a[len(self.a)-1],"b":del self.b[len(self.b)-1],"c":del self.c[len(self.c)-1]}
#		cancella_anello[s]
			
							
	
	def main(self):
		print "\n Situazione Originale"
		print "\nPaletto sorgente\n"
		print self.a
		print "\nPaletto destinazione\n"
		print self.b
		print "\nPaletto di transizione\n"
		print self.c


		print "Ecco i movimenti\n\n"
		self.hanoi(self.rings,self.d,self.s,self.t)

		print "\n Situazione Finale"
		print "\nPaletto sorgente\n"
		print self.a
		print "\nPaletto destinazione\n"
		print self.b
		print "\nPaletto di transizione\n"
		print self.c
		
		print "\n\nProblema risolto in "+str(self.move) +" mosse" 

		
if __name__ == "__main__":
	print "\nHanoi Resolution\n"
	print "\nAssumo 'a' paletto sorgente, 'b' destinazione e 'c' di transizione"
	print "\nInserisci il numero di anelli"
	ringsU = raw_input()
	
	# si suppone
	# a - paletto sorgente	
	# b - paletto destinazione
	# c - paletto di transizione

        ha = hanoi(ringsU,"b","a","c")
        ha.main()