cuvinte

Se consideră un șir de cuvinte separate două câte două printr-un spațiu. Fiecare cuvânt este caracterizat prin numărul de ordine care reprezintă poziția lui în șirul de cuvinte (primul cuvânt are numărul de ordine $1$). Unui cuvânt $i$ se pot aplica în mod repetat următoarele transformări: primul caracter al cuvântului (cel mai din stânga) se șterge de acolo și se adaugă după ultimul caracter din cuvânt. Astfel, dintr-un cuvânt $s$ cu $k$ caractere se pot obține alte $k-1$ cuvinte pe care le numim cuvinte obținute din transformarea cuvântului $s$. De exemplu, dintr-un cuvânt format din $4$ caractere $c_1 c_2 c_3 c_4$, cuvintele obținute prin transformarea lui sunt: $c_2 c_3 c_4 c_1$, $\ c_3 c_4 c_1 c_2$, $\ c_4 c_1 c_2 c_3$.

Se caută în șirul de cuvinte prima pereche de cuvinte vecine $(a,b)$, în care al doilea cuvânt din pereche (cuvântul $b$) este identic cu un cuvânt obținut din transformarea lui $a$. Dacă există o astfel de pereche, se șterge cuvântul $b$ din șir. Prin ștergerea cuvântului $b$ din șir, acesta va avea mai puțin cu un cuvânt! Se repetă operația de căutare de mai sus până când în șirul rămas nu mai există o pereche $(a,b)$ de cuvinte vecine, astfel încât $b$ să fie obținut prin transformarea lui $a$.

Se știe că pe parcursul modificărilor, cuvintele nu-și schimbă numerele de ordine pe care le-au avut inițial.

Cerință

Scrieți un program care să citească șirul de cuvinte și să afișeze:

1. numărul de ordine al primului cuvânt șters sau valoarea $0$ în cazul în care nu se șterge niciun cuvânt
2. numerele de ordine ale cuvintelor rămase după finalizarea operațiilor de modificare.

Date de intrare

Fișierul de intrare cuvinte.in conține o singură linie pe care se află șirul de cuvinte separate două câte două printr-un spațiu.

După ultimul cuvânt din șir există caracterul !.

Date de ieșire

Fișierul de ieșire cuvinte.out va conține pe prima linie numărul de ordine al primului cuvânt șters sau valoarea $0$ în cazul în care nu se șterge niciun cuvânt.

Pe a doua linie vor fi scrise numerele de ordine ale cuvintelor rămase în final în șirul de cuvinte, separate prin câte un spațiu. Aceste numere pot fi scrise în orice ordine.

Restricții și precizări

• Fiecare cuvânt are maxim $10$ caractere, iar în șirul inițial nu există mai mult de $25$ cuvinte.
• Șirul de cuvinte inițial este format din cel puțin un cuvânt. O pereche de cuvinte vecine $(a,b)$, din șirul de cuvinte este caracterizată prin faptul că, după cuvântul $a$ se afla imediat cuvântul $b$.
• Se acordă punctaje parţiale: cerinţa 1 este $40\%$ din punctaj, iar cerinţa 2 este $60\%$ din punctaj.

Exemplu

cuvinte.in

alfa faal alfa fala lafa afal calfa calfa!

cuvinte.out

2
1 3 4 7 8

Explicație

Cuvintele obținute prin transformarea cuvântului alfa sunt: lfaa, faal, aalf.

Prima pereche de cuvinte vecine care îndeplinesc cerințele sunt cuvintele cu numerele de ordine $1$ și $2$. Va fi șters cuvântul cu numărul de ordine $2$.

Șirul rezultat este format din următoarele $7$ cuvinte: alfa, alfa, fala, lafa, afal, calfa, calfa. Prima pereche care îndeplinește cerințele din noul șir este perechea formată din cuvintele fala și lafa, având numerele de ordine $4$ și $5$, pentru că lista de cuvinte obținute prin transformarea cuvântului fala sunt: alaf, lafa, afal. Se va șterge cuvântul cu numărul de ordine $5$.

Șirul rezultat după ștergere este: alfa, alfa, fala, afal, calfa, calfa. Prima pereche care îndeplinește cerințele problemei în noul șir este fala și afal. Se șterge afal cu numărul de ordine $6$.

Șirul rezultat după ștergere este: alfa, alfa, fala, calfa, calfa. În acest șir nu se mai găsește nicio pereche care să îndeplinească cerințele. Au rămas deci cuvintele: alfa, alfa, fala, calfa, calfa, care au numerele de ordine $1$, $3$, $4$, $7$, $8$.