perle

Time limit: 0.1s Memory limit: 64MB Input: perle.in Output: perle.out

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ă 33 tipuri de perle normale (le vom nota cu 11, 22 şi 33) şi 33 tipuri de perle magice (le vom nota cu AA, BB şi CC). Perlele magice sunt deosebite prin faptul că se pot transforma în alte perle (una sau mai multe, normale sau magice):

  • Perla magică de tipul AA se poate transforma în orice perlă normală (una singură);
  • Perla magică de tipul BB se poate transforma într-o perlă normală de tipul 22 şi una magică de tipul BB, sau într-o perlă normală de tipul 11, una magică de tipul AA, una normală de tipul 33, una magică de tipul AA şi una magică de tipul CC;
  • Perla magică de tipul CC se poate transforma într-o perlă normală de tipul 22 sau într-o perlă normală de tipul 33, una magică de tipul BB şi una magică de tipul CC sau într-o perlă normală de tipul 11, una normală de tipul 22 şi una magică de tipul AA.

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 BB ş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 NN, reprezentând numărul de şiruri din fişierul de intrare;
  • Urmează NN linii; a ii-a linie dintre cele NN descrie şirul ii, printr-o succesiune de numere naturale despărţite de câte un spaţiu. Primul număr reprezintă lungimea şirului LiL_i, iar următoarele LiL_i numere sunt tipurile de perle normale, în ordine, de la stânga la dreapta.

Date de ieșire

Fişierul perle.out va conţine NN linii. Pe linia ii se va scrie un singur număr 11 sau 00 (11 dacă se poate obţine şirul respectiv (al ii-lea) şi 00 dacă nu se poate).

Restricții și precizări

  • 1N101 \leq N \leq 10;
  • 1Li10 0001 \leq L_i \leq 10 \ 000, pentru oricare ii;

Exemplu

perle.in

3
8 2 1 1 3 2 1 2 3
2 2 2
1 3

perle.out

1
0
1

Log in or sign up to be able to send submissions!