h2. Date de intrare

Fişierul de intrare $pitici5.in$ contine pe prima linie valoarea $N$, reprezentand numarul de pitici si un caracter $C$ ce reprezinta culoarea primului pitic care va ramane primul si dupa reasezare, ceilalti urmand sa se aseze in spatele lui. Acest caracter va avea fie valoarea $'A'$, ce va insemna ca primul pitic are culoarea $alba$, fie valoarea $'B'$ ceea ce va inseamna ca acesta va avea culoarea $neagra$.

Fişierul de intrare $pitici5.in$ contine pe prima linie valoarea $N$, reprezentand numarul de pitici si un caracter $C$ ce reprezinta culoarea primului pitic care va ramane primul si dupa reasezare, ceilalti urmand sa se aseze in spatele lui. Acest caracter va avea fie valoarea $'A'$, ce va insemna ca primul pitic are culoarea $alba$, fie valoarea $'N'$ ceea ce va inseamna ca acesta va avea culoarea $neagra$.

Pe urmatoarele $N$ linii se vor afla exact doua caractere separate prin cate un spatiu. Fiecare din aceste perechi de caractere vor fi informatiile corespunzatoare fiecarui pitic. Primul caracter va pastra culoarea pe care vrea sa o aiba piticul in fata sa, iar cel de-al doilea caracter va pastra culoarea proprie a piticului respectiv.

h2. Restricţii
* $1 ≤ N ≤ 100 000$

* Se garanteaza ca intotdeauna exista o asezare posibila care sa respecte restrictiile tuturor piticilor.
* Spunem că un drum A=(a ~1~,a ~2~,..,a ~N~) este mai mic lexicografic decât un drum B=(b ~1~, b ~2~,..,b ~N~) dacă există o poziţie p astfel încât x ~p~ < y ~p~ şi x ~1~ = y ~1~, x ~2~ = y ~2~,..., x ~p-1~ = y ~p-1~.

* Se garanteaza ca intotdeauna exista o asezare posibila astfel incat sa se respecte restrictiile celor $N$ pitici.
* Spunem că un sir A=(a ~1~,a ~2~,..,a ~N~) este mai mic lexicografic decât un sir B=(b ~1~, b ~2~,..,b ~N~) dacă există o poziţie p astfel încât x ~p~ < y ~p~ şi x ~1~ = y ~1~, x ~2~ = y ~2~,..., x ~p-1~ = y ~p-1~.

h2. Exemplu

h3. Explicaţie

Primul pitic din sir este deja fixat si are culoarea $alba$. Urmatorii $N$ pitici se vor reaseza in felul urmator: cel de-al $doilea$ pitic va fi $primul$, cel de-al $patrulea$ pitic va deveni al $doilea$, $primul$ pitic va fi al $treilea$ dupa reasezare si asa mai departe... Sirul pozitiilor initiale, rezultat dupa asezarea minima lexicografica, care respecta toate restrictiile celor $N$ pitici este $2 4 1 3 6 5$. Mai sunt posibile si alte reasezari ale piticilor (de exemplu $2 4 1 5 3 6$), dar aceste siruri nu sunt minime lexicografic.

Primul pitic din sir este deja fixat si are culoarea $alba$. Urmatorii $N$ pitici se vor reaseza in felul urmator: cel de-al $doilea$ pitic va fi $primul$, cel de-al $patrulea$ pitic va deveni al $doilea$, $primul$ pitic va fi al $treilea$ si asa mai departe... Sirul pozitiilor initiale, rezultat dupa asezarea minima lexicografica, care respecta toate restrictiile celor $N$ pitici este $2 4 1 3 6 5$. Mai sunt posibile si alte reasezari ale piticilor (de exemplu $2 4 1 5 3 6$), dar sirurile asociate acestor reasezari nu sunt minime lexicografic.

== include(page="template/taskfooter" task_id="pitici5") ==

9810