ProtoZuma este un joc foarte simplu, în care un şir S de simboluri (simbolurile sunt numerotate de la stânga la dreapta, începând cu indicele 1) este lovit în poziţia i de o ghiulea. Imediat după lovitură se produce „explozia”, după următoarea regulă:

• Dacă simbolurile din poziţiile i-1, i, i+1 nu sunt egale între ele, nu se întâmplă nimic – şirul S rămâne intact.
  Exemplu: AAABB este lovit în poziţia 4. Rezultat: AAABB

• Dacă simbolurile din poziţiile i-1, i, i+1 sunt egale, din şir se elimină toată secvenţa de simboluri egale care le conţine, iar fragmentele rămase se unesc.
  Exemplu: BBAAAAACCC este lovit în poziţia 4 Rezultat: BBCCC

• Atât timp cât după explozie în poziţia în care se unesc fragmentele se formează o secvenţă de cel puţin 3 litere egale, explozia se repetă.
  Exemplu: DBBAAAAABCCC este lovit în poziţia 6
  Rezultat: DBB <-> BCCC, explozia se repetă, rezultat  final DCCC

Cerinţă

Scrieţi un program, care să determine şirul în care se transformă şirul iniţial S după lovitura unei ghiulele.

Date de intrare

Fişierul de intrare zuma.in va conţine pe prima linie un număr natural – valoarea i a poziţiei în care loveşte ghiuleaua. Linia a doua a fişierului conţine şirul S.

Date de ieşire

Fişierul de ieşire zuma.out va conţine o singură linie pe care va fi scris şirul S după lovitură şi explozii.

Restricţii

• Lungimea S nu va depăşi 200 caractere.
• 1 < i < lungimea şirului S

Exemple

zuma.in	zuma.out
12 AABBCCCCBRQQQAA	AABBCCCCBRAA

prof. Sergiu Corlat

Liceul Orizont Chisinau

scorlat@gmail.com