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 c1c2c3c4, cuvintele obţinute prin transformarea lui sunt: c2c3c4c1, c3c4c1c2, c4c1c2c3.

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:

a) numărul de ordine al primului cuvânt şters sau valoarea 0 în cazul în care nu se şterge niciun cuvânt
b) numerele de ordine ale cuvintelor rămase după finalizarea operaţiilor de modificare.

Date de intrare

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

Date de ieșire

Fișierul de ieșire cuvinte4.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 numerele de ordine ale cuvintelor rămase în final în şirul de cuvinte, despărţite două câte două printr-un spaţiu.

Restricții și precizări

• După ultimul cuvânt din şirul iniţial există caracterul !
• 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.

Exemplu:

cuvinte4.in

alfa faal alfa fala lafa afal calfa calfa!

cuvinte4.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.