Jaś i Małgosia wymyślili sobie pewną grę. Na początku
muszą wygenerować sobie specyficzną planszę o wysokości 1
i dość dużej szerokości. Generacja planszy składa się z
kilku etapów. W pierwszym, losują a0 cyfr i wpisują
je w kolejne pola planszy bazowjej, zwanej inaczej planszą
stopnia 0. Następnie losują tzw. ciąg generujący
a1, a2, ..., aN.
Dalej plansza budowana jest zgodnie z zasadą, że plansza stopnia i
(i = 1..N) powstaje poprzez ułożenie obok
siebie ai planszy stopnia i–1
z "zanegowanymi" wszsytkimi cyframi
(przez negację cyfry c rozumiemy zamienienie jej na cyfrę 9-c).
Dopiero plansza stopnia N jest tą planszą właściwą, na której
odbędzie się gra. Jej pola są ponumerowane od lewej do prawej kolejnymi
liczbami całkowitymi od 1 do
a0*a1*...*aN.
Oczywiście nie ma wątpliwości, że w ten sposób mogą powstać bardzo
duże plansze. Na szczęscie Jaś i Małgosia generują ją na komputerze,
a nie na papierze, stąd stworzenie ogromnej planszy nie jest wielkim
problemem.
Przykład. Mając planszę bazową (planszę stopnia 0) 12 oraz trójelementowy ciąg tworzący (2,3,2) otrzymamy kolejno plansze: stopnia 1 8787, stopnia 2 121212121212 oraz stopnia 3 (planszę właściwą) 878787878787878787878787.
Mając już wygenerowaną planszę dzieci obierają sobie dwa różne pola,
które mają taką samą cyfrę. Pole o numerze mniejszym jest polem
startowym (na którym stawiamy wirtualny pionek), a o numerze większym metą.
W grze bierze udział jeden pionek (wspólny dla obu graczy), który na początku
ustawiany jest na polu startowym. Gracze wykonują ruchy
na zmianę. Ruch polega na przesunięciu pionka w prawo na najbliższe pole
mające taką samą cyfrą co pole, na którym akutalnie stoi pionek.
Kto postawi pionek na polu mety ten wygrywa.
Sposób obrania startu i mety jest częścią strategii gry. Jak się okazuje jest to najważniejszą częścią, gdyż samo wykonywanie ruchów jest mechaniczne i nic do gry nie wnosi, a jest tylko sposobem weryfikacji strategii wyboru pól. Ale nie będziemy specjalnie w nią ingerować, żeby nie psuć Jasiowi i Małgosi zabawy (dlatego nawet nie będziemy tu omawiać zasad wybierania pól). Jedynie chcemy im pomóc uprościć ostatnią fazę gry, żeby biedaczki nie musiały się męczyć z wykonywaniem ruchów na ogromnej planszy.
Twoim zadaniem jest dla danej planszy (opisanej przez planszę bazową oraz ciąg generujący) oraz dla danych pól startu i mety określić czy zaczynający wygrywa.
W pierwszej linii wejścia znajduje się jedna liczba całkowita dodatnia
B, mowiąca ile plansz znajduje się dalej na wejściu.
W pierwszej linii opisu planszy znajduje się niepusty ciąg cyfr o długości
co najwyżej 255 znaków - jest to plansza bazowa. W drugiej linii znajduje
się liczba N (1 ≤ N ≤ 100).
W trzeciej linii jest N dodatnich liczb całkowitych, stanowiących
ciąg generujący planszę. Te dane definiują planszę, na której będą
grać Jaś i Małgosia. Mamy gwarancję, że powstała plansza ma co najmniej
2 pola i conajwyżej 2.100.000.000.
Z kolei w czwartej linii opisu planszy znajduje się liczba G
(1 ≤ G ≤ 10), mówiąca ile gier zostanie
rozegranych na niej. Następnie pojawia się G linii zawierających
po 2 różne liczby całkowite, będące (poprawnymi) numerami pól obranymi
przez dzieci.
Dla każdej planszy należy wypisać na wyjściu kilka linii. Pierwsza z nich powinna być postaci PLANSZA <nr> (gdzie <nr> to numer planszy licząc od 1). Dalej powinno pojawić się tyle linii ile było gier do rozegrania na tej planszy, każda postaci GRA <nr>: <odpowiedz>, gdzie (gdzie <nr> to numer gry licząc od 1, a <odpowiedz> to słowo TAK lub NIE mówiące czy rozpoczynający daną grę wygrywa). Na samym końcu odpowiedzi dla każdej planszy powinna pojawić się linia pusta.
2 12 3 2 3 2 3 1 23 2 22 14 16 121 2 4 3 2 6 15 5 14
PLANSZA 1 GRA 1: TAK GRA 2: NIE GRA 3: TAK PLANSZA 2 GRA 1: NIE GRA 2: TAK