Ana şi Bogdan joacă un joc care lor li se pare interesant. Ana se gândeşte la un şir format din N litere din mulţimea {′A′, ′B′}. După care Ana face o serie de afirmaţii (propoziţii adevărate) de tipul următor:
Pe poziţia x1 se află litera L1 sau pe poziţia x2 se află litera L2.
Literele L1 şi L2 din afirmaţie aparţin mulţimii {′A′, ′B′}.
Bogdan trebuie să ghicească şirul de caractere la care s-a gândit Ana pe baza afirmaţiilor ei.
Cerinţă
Scrieţi un program care să construiască un şir de lungime N format numai din literele ′A′ şi ′B′, şir pentru care toate afirmaţiile Anei sunt corecte.
Date de intrare
Fişierul de intrare guess.in conţine pe prima linie numărul natural N reprezentând lungimea şirului. Pe cea de a doua linie este scris un număr natural P reprezentând numărul de afirmaţii. Pe fiecare dintre următoarele P linii este scrisă câte o afirmaţie sub forma: x1 L1 x2 L2
unde x1 şi x2 sunt două numere naturale cuprinse între 1 şi N, iar L1 şi L2 sunt două litere din mulţimea {′A′, ′B′}. Valorile x1, L1, x2, L2 sunt separate prin câte un singur spaţiu.
Date de ieşire
Fişierul de ieşire guess.out va conţine o singură linie pe care va fi scris un şir de lungime N format numai din literele ′A′ şi ′B′, şir pentru care toate afirmaţiile din fişierul de intrare sunt corecte.
Restricţii
2 ≤ N ≤ 1000
1 ≤ P ≤ 10000
Poziţiile în şir sunt numerotate de la 1 la N.
Pentru datele de test există întotdeauna soluţie, nu neapărat unică.
Exemple
guess.in
guess.out
3
6
1 A 2 A
2 A 3 A
1 A 3 A
2 B 3 B
1 A 2 B
1 B 3 A