Problema Hanoi

Jocul turnului din Hanoi este un puzzle ce constă în găsirea soluției următoarei probleme. Avem trei tije, A, B și C. Inițial, pe tija A sunt amplasate n discuri de diametre variabile, în ordine descrescătoare a razei de la bază; celelalte două tije sunt goale (exact ca în figura de mai jos, cu n = 8 discuri). Scopul jocului este de a muta toate discurile de pe tija A pe tija C (folosind ca tijă ajutătoare B), respectând regulile următoare:

• doar un singur disc poate fi mutat, la un moment dat;
• fiecare mutare constă în luarea celui mai de sus disc de pe o tijă și glisarea lui pe o altă tijă, chiar și deauspra altor discuri care sunt deja prezente pe acea tijă;
• un disc de rază mai mare nu poate fi poziționat deasupra unui disc mai mic.

Cerință

Se dă numărul natural n. Presupunând că pe tija A se află inițial n discuri amplasate corect, să se determine mutările necesare pentru ca toate discurile să fie mutate pe tija C, respectând regulile jocului.

Date de intrare

Programul citește de la tastatură numărul natural n, ce reprezintă numărul de discuri aflate pe tija A.

Date de ieșire

Programul afișează pe ecran mutările necesare pentru a rezolva corect problema. Mutările separate sunt plasate câte una pe linie și sunt notate astfel: SRC DEST (cu un spațiu între cele două) cu semnificația: mutăm un disc de pe tija SRC pe tija DEST (unde SRC și DEST pot avea valorile A, B sau C).

Restricții și precizări

• 1 ≤ n ≤ 15

Exemplu