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

Intr-o padure traiesc doua tipuri de pitici: de culoare $alba$ si de culoare $neagra$. Ei doresc sa se aseze in sir indian, dar din pacate pentru fiecare pitic are o pretentie si anume vrea sa vada in fata lui un pitic de o anume culoare, ori alba, ori neagra. Cum ei sunt foarte incapatanati vor sa gaseasca o asezare care sa respecte pretentiile fiecaruia dintre ei, dar cum ei nu stiu algoritmica va roaga pe voi sa le scrieti un program prin care sa creati pentru ei o astfel de asezare. Ei am mentionat daca veti reusi sa ii ajutati va vor oferi 100 de puncte.

Intr-o padure traiesc doua tipuri de pitici: de culoare $alba$ si de culoare $neagra$. Ei doresc sa se aseze in sir indian, dar din pacate fiecare pitic are o pretentie si anume vrea sa vada in fata lui un pitic de o anume culoare, ori alba, ori neagra. Cum ei sunt foarte incapatanati vor sa gaseasca o asezare care sa respecte pretentiile fiecaruia dintre ei, dar cum nici unul nu stie algoritmica va roaga pe voi sa le scrieti un program prin care sa generati pentru ei o astfel de asezare. Ei au mentionat ca daca veti reusi sa ii ajutati va vor oferi 100 de puncte.

h1. Cerinta

Fiind dat numarul $N$ de pitici si pe rand cate un pitic, in ordinea in care se afla acum (ei au apucat sa se alinieze in sir indian si apoi si-au dat seama ca unii dintre ei au anumite pretentii), trebuie sa gasiti o asezare posibila care respecta toate restrictiile de mai sus. Mai mult decat atat, putem sa-i atribuim fiecarui pitic un numar natural in functie de pozitia pe care se afla in sir, mai precis piticului de pe pozitia $1$ i se atribuie numarul $1$, piticului de pe pozitia $2$ i se atribuie numarul $2$ si asa mai departe... Se cere ca sirul de valori atribuite fiecarui pitic, obtinut dupa reasezarea acestora, sa fie minim lexicografic. Se mai stie ca primul pitic este de culoare $G$ si nu se afla printre piticii initiali si mai mult decat atat nu are nicio pretentie.

Fiind dat numarul $N$ de pitici si pe rand cate un pitic, in ordinea in care se afla acum trebuie sa gasiti o asezare posibila care respecta toate restrictiile de mai sus. Mai mult decat atat ei sunt numerotati cu valori distincte de la $1$ la $N$ si se cere ca sirul acestor valori, obtinut dupa reasezarea piticilor, sa fie minim lexicografic. Se mai stie ca primul pitic este de culoare $C$, are numarul de ordine $0$ si nu se afla printre piticii initiali, iar mai mult decat atat nu are nicio pretentie.

h2. Date de intrare

Fişierul de intrare $pitici5.in$ contine pe prima linie valoarea $N$, reprezentand numarul de pitici si un caracter $G$ ce reprezinta culoarea primului pitic care va ramane primul si dupa reordonare, 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 reordonare, 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.

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~.
h2. Exemplu