//------------
// Introduction to Programming Using Java: An Object-Oriented Approach
//	Arnow/Weiss
//------------
import  java.io.*;
import  java.util.*;

public class Towers {
	public static void main(String[] a) {
		if (a.length!=1)
			System.err.println("Usage: java Towers <number of disks> ");
		else {
			int nDisks = Integer.parseInt(a[0]);
			Towers   th = new Towers(new TowerDisplay(), nDisks);
			th.solveIt();
		}
	}

	public Towers(TowerDisplay td, int nDisks) {
		this.td = td;
		this.nDisks = nDisks;
		td.setup(nDisks,1);
	}

	public void solveIt() {
		solveIt(nDisks, 1, 3);
	}

	private void solveIt(int nDisks, int source, int target) {
		if (nDisks<=0)
			return;
		int    holdingTower = getholdingTower(source,target);
		solveIt(nDisks-1,source,holdingTower);
		td.displayMove(source,target);
		solveIt(nDisks-1,holdingTower,target);
	}

	private int getholdingTower(int source, int target) {
		if (source==2 && target==3 || source==3 && target==2)
			return 1;
		if (source==1 && target==3 || source==3 && target==1)
			return 2;
		return 3;
	}

	private    int            nDisks;
	private    TowerDisplay   td;
}

class TowerDisplay {
	public TowerDisplay() {
	}

	public void setup(int nDisks, int source) {
		if (nDisks>9)
			nDisks = 9;
		tower = new String[4];
		tower[1] = "";
		tower[2] = "";
		tower[3] = "";
		tower[source] = "123456789".substring(0,nDisks);
	}

	public void displayMove(int from, int to) {
		System.out.println("MOVE from "+from+" to "+to);
		int fromLast = tower[from].length()-1;
		tower[to] = tower[to].concat(tower[from].
		substring(fromLast));
		tower[from] = tower[from].substring(0,fromLast);
		System.out.println("   tower 1:"+tower[1]);
		System.out.println("   tower 2:"+tower[2]);
		System.out.println("   tower 3:"+tower[3]);
	}

	private    String[]   tower;
}