Mechagodzilla
Limit pamięci: 128 MB
Przedwczoraj sam byłeś świadkiem, jak Godzilla zjadała kable z Modą na sukces.
Władze Bajtołów Dolnych postanowiły powiedzieć Godzilli stanowcze nie.
Do walki z Godzillą zaprzęgli Mechagodzillę, która w odróżnieniu od tej pierwszej
jest robotem, którym mogą sterować.
Mechagodzilla ma stanów, w których może się znajdować, w tym jeden stan
początkowy i pewien podzbiór stanów bojowych.
W każdym stanie Mechagodzilla może wykonać jedną z instrukcji (instrukcje są
oznaczone wielkimi literami od A do Z),
które powodują zmianę stanu na inny.
Jeśli Mechagodzilla jest w stanie i otrzyma instrukcję , to przechodzi do stanu .
Grupa informatłuków pisze program dla Mechagodzilli.
Jest to ciąg instrukcji, które Mechagodzilla wykonuje kolejno, zaczynając od stanu początkowego.
Powiemy, że program jest dobry, jeśli Mechagodzilla po jego zakończeniu znajdzie się w stanie bojowym.
Informatłucy mają to do siebie, że co chwilę robią w programie jakieś poprawki,
polegające na zamianie miejscami pewnych dwóch instrukcji.
Twoim zadaniem jest odpowiadać na pytania, czy po danej zamianie program jest dobry czy nie.
Wejście
Pierwszy wiersz wejścia zawiera cztery liczby naturalne (, , , ), oznaczające odpowiednio liczbę stanów,
liczbę stanów bojowych, długość programu i liczbę poprawek dokonanych przez informatłuków.
Następny wiersz zawiera liczb naturalnych (), które oznaczają numery stanów
bojowych. Stan o numerze to stan początkowy.
Następne wierszy zawiera po liczb naturalnych (), oznaczających,
że jeśli Mechagodzilla będzie w stanie i dostanie instrukcję , to przejdzie do stanu .
Następny wiersz zawiera napis złożony z wielkich liter alfabetu angielskiego, oznaczających program
dla Mechagodzilli.
Następne wierszy zawiera po dwie liczby naturalne (), oznaczające kolejne
poprawki informatłuków. Każda taka poprawka oznacza, że instrukcje na pozycjach i
zamieniają się miejscami.
Wyjście
Na wyjściu należy wypisać wierszy.
Są to odpowiedzi na pytania, czy po kolejnych poprawkach program jest dobry (TAK jeśli tak,
NIE w przeciwnym wypadku).
Przykład
Dla danych wejściowych:
3 1 5 2
3
1 1 1 1 1 1 1 1 1 1 3 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 3 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1
TKOAN
1 3
2 5
poprawną odpowiedzią jest:
NIE
TAK
Autor zadania: Dariusz Leniowski.