puzzle

Unul dintre jocurile preferate ale lui Temistocle este un puzzle în care el are la dispoziţie un cuvânt, fiecare literă a acestuia fiind scrisă pe câte o plăcuţă. Iniţial, toate plăcuţele sunt amestecate şi aşezate într-o ordine oarecare pe un suport liniar, poziţiile plăcuţelor fiind numerotate de la stânga la dreapta, începând cu $1$.

Dacă se alege o plăcuţă drept pivot, se obţin două grupe:

• grupa $1$ - formată din toate plăcuţele din stânga plăcuţei-pivot, inclusiv aceasta;
• grupa $2$ - formată din toate plăcuţele din dreapta plăcuţei-pivot, fără aceasta.

După alegerea plăcuţei-pivot, toate plăcuţele din grupa $1$, dacă există, se deplasează circular spre stânga cu exact o poziţie, iar toate plăcuţele din grupa $2$, dacă există, se deplasează circular spre dreapta, cu exact o poziţie, ca în figura de mai jos, după care plăcuţele se renumerotează, de la stânga la dreapta, începând cu $1$.

Cerință

Scopul jocului este ca prin alegerea unui şir potrivit de plăcuţe-pivot să se obţină o aşezare a plăcuţelor, astfel încât cuvântul format din literele scrise pe acestea, de la stânga la dreapta, să fie identic cu cuvântul corect.

Date de intrare

În fişierul puzzle.in se află

• pe prima linie, cuvântul corect;
• pe a doua linie, cuvântul format prin aşezarea iniţială a plăcuţelor.

Date de ieşire

În fişierul puzzle.out se vor scrie, separate prin câte un spaţiu, numerele naturale, reprezentând poziţiile plăcuţelor-pivot, în ordinea alegerii lor. Şirul se încheie cu numărul $0$, care nu corespunde niciunei plăcuţe, ci reprezintă finalul jocului.

Restricții și precizări

• Fiecare cuvânt are cel mult $250$ de litere.
• Dacă există mai multe soluţii, se va furniza una singură, nu neapărat optimă.

Exemplul 1

puzzle.in

abc
bac

puzzle.out

2 0

Explicație

pivot - $2$
ba | c $\rightarrow$ ab | c

Exemplul 2

puzzle.in

abcabc
aabbcc

puzzle.out

6 2 2 0

Explicație

pivot - $6$
aabbcc | $\rightarrow$ abbcca |
pivot - $2$
ab | bcca $\rightarrow$ ba | abcc
pivot - $2$
ba | abcc $\rightarrow$ ab | cabc

Exemplul 3

puzzle.in

xyz
xyz

puzzle.out

0

Explicație

Cuvântul corespunzător plăcuţelor este cel corect.