Słowa
Limit pamięci: 64 MB
Niech będzie funkcją określoną na napisach złożonych z cyfr 0 i 1.
Funkcja przekształca napis , zastępując (niezależnie i równocześnie) każdą cyfrę
0 przez 1 i każdą cyfrę 1 przez napis .
Na przykład ,
(tzn. funkcja zastosowana do pustego napisu jest pustym napisem).
Zauważmy, że jest różnowartościowa.
Przez oznaczmy -krotne złożenie funkcji ze sobą.
W szczególności, to funkcja identycznościowa .
Interesują nas napisy postaci dla
Oto kilka pierwszych takich napisów:
,
,
,
,
,
.
Mówimy, że napis
jest
podsłowem napisu
, jeżeli występuje w nim jako
spójny (tj. jednokawałkowy) podciąg.
Mamy dany ciąg liczb naturalnych
.
Celem zadania jest sprawdzenie, czy napis postaci
jest podsłowem
dla pewnego
.
Przy tym operacja
oznacza sklejenie (konkatenację) napisów.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą , ,
oznaczającą liczbę przypadków testowych do rozważenia.
Pierwszy wiersz opisu każdego przypadku zawiera jedną liczbę całkowitą , .
W drugim wierszu opisu znajduje się nieujemnych liczb całkowitych
pooddzielanych pojedynczymi odstępami.
Suma liczb z drugiego wiersza każdego przypadku jest nie większa niż .
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy, po jednym dla każdego
przypadku testowego.
Wiersz odpowiadający danemu przypadkowi testowemu powinien zawierać jedno słowo:
TAK - jeśli w tym przypadku
jest podsłowem dla pewnego , lub NIE w przeciwnym razie.
Przykład
Dla danych wejściowych:
2
2
1 2
2
2 0
poprawną odpowiedzią jest:
TAK
NIE
Wyjaśnienie do przykładu:
Słowo z pierwszego przypadku testowego to - jest ono podsłowem
na przykład słowa .
W drugim przypadku testowym występuje słowo , które nie jest
podsłowem żadnego słowa postaci .
Autorzy zadania: Wojciech Rytter, Bartosz Walczak.