Skoczki
Limit pamięci: 64 MB
Na cyklicznej taśmie jest pól.
Niektóre z nich są pomalowane na czarno, a niektóre na biało.
Twoim zadaniem jest pomalowanie wszystkich pól na czarno.
Do malowania używasz skoczków - skaczących robocików zamoczonych w czarnej farbie.
Jeżeli skoczek skoczy na jakieś białe pole, to przemalowuje je na czarno.
Skoczki nie mogą skakać na czarne pola.
Do pomalowania planszy możesz użyć dowolnej liczby skoczków.
Dla każdego skoczka wybierasz dowolne białe pole startowe, muszą być one parami różne.
Każdy skoczek musi wykonać przynajmniej jeden skok i wrócić na pole, z którego wystartował.
Skoczek maluje swoje pole początkowe dopiero w ostatnim skoku.
Wszystkie skoczki są identyczne - mają ten sam zestaw możliwych skoków, opisany zbiorem .
Skoczek znajdujący się w danym polu może wykonać jeden spośród dostępnych ruchów, o ile skok ten spełnia powyższe wymagania.
-ty spośród nich polega na skoku o pól zgodnie z ruchem wskazówek zegara.
Dla danej taśmy i specyfikacji skoczków, należy odpowiedzieć na pytanie:
"Czy da się przemalować taśmę na czarno, zachowując powyższe warunki?"
Wejście
W pierwszym wierszu wejścia znajduje się liczba naturalna () oznaczająca liczbę zestawów
testowych.
Następne wiersze opisują kolejne zestawy testowe.
W pierwszym wierszu znajdują się dwie liczby całkowite i
(); to długość taśmy, zaś - liczba możliwych długości skoków.
Kolejny wiersz zawiera napis złożony z liter B i C, będący opisem
cyklicznej taśmy (B - pole białe, C - pole czarne).
Następne wierszy zawiera po jednej liczbie naturalnej (), oznaczającej
jeden z możliwych skoków skoczka.
Wyjście
Na wyjściu należy wypisać dla każdego testu jeden wiersz. Powinien on zawierać jedno słowo: TAK,
jeśli da się pomalować taśmę na czarno, lub NIE w przeciwnym wypadku.
Przykład
Dla danych wejściowych:
2
4 2
BCBB
1
2
4 1
BCBB
2
poprawną odpowiedzią jest:
TAK
NIE
Autor zadania: Piotr Niedźwiedź.