Graniţa nu se trece uşor. Asta pentru că Balaurul Arhirel (mare pasionat de informatică) nu lasă pe nimeni să treacă decât după ce răspunde la nişte întrebări…
În acea ţară există 3 tipuri de perle normale (le vom nota cu 1, 2 şi 3) şi 3 tipuri de perle magice (le vom nota cu A, B şi C). Perlele magice sunt deosebite prin faptul că se pot transforma în alte perle (una sau mai multe, normale sau magice).
Perla magică de tipul A se poate transforma în orice perlă normală (una singură).
Perla magică de tipul B se poate transforma într-o perlă normală de tipul 2 şi una magică de tipul B, sau într-o perlă normală de tipul 1, una magică de tipul A, una normală de tipul 3, una magică de tipul A şi una magică de tipul C.
Perla magică de tipul C se poate transforma într-o perlă normală de tipul 2 sau într-o perlă normală de tipul 3, una magică de tipul B şi una magică de tipul C sau într-o perlă normală de tipul 1, una normală de tipul 2 şi una magică de tipul A.
Ca să rezumăm cele de mai sus putem scrie: A -> 1 | 2 | 3
B -> 2B | 1A3AC
C -> 2 | 3BC | 12A
Balaurul Arhirel ne lasă la început să ne alegem o perlă magică (una singură), iar apoi folosind numai transformările de mai sus trebuie să obţinem un anumit şir de perle normale. Când o perlă magică se transformă, perlele din stânga şi din dreapta ei rămân la fel (şi în aceeaşi ordine). De asemenea ordinea perlelor rezultate din transformare este chiar cea prezentată mai sus.
De exemplu, dacă balaurul ne cere să facem şirul de perle 21132123, putem alege o perlă magică de tipul B şi următorul şir de transformări: B -> 2B -> 21A3AC -> 21A3A12A -> 21132123.
Întrucât Balaurul nu are prea multă răbdare, el nu ne cere decât să spunem dacă se poate sau nu obţine şirul respectiv de perle.
Cerinţă
Să se determine pentru fiecare şir de intrare dacă se poate obţine prin transformările de mai sus sau nu (alegând orice primă perlă magică, la fiecare şir).
Date de intrare
Fişierul de intrare perle.in are următoarea structură:
– pe prima linie numărul N, reprezentând numărul de şiruri din fişierul de intrare;
– urmează N linii; a i-a linie dintre cele N descrie şirul i, printr-o succesiune de numere naturale despărţite de câte un spaţiu. Primul număr reprezintă lungimea şirului Li, iar următoarele Li numere sunt tipurile de perle normale, în ordine, de la stânga la dreapta.
Date de ieşire
Fişierul de ieşire perle.out va conţine N linii. Pe linia i se va scrie un singur număr 1 sau 0 (1 dacă se poate obţine şirul respectiv (al i-lea) şi 0 dacă nu se poate).