8499번 - Mechagodzilla 다국어

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 n 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 26 instrukcji (instrukcje są oznaczone wielkimi literami od A do Z), które powodują zmianę stanu na inny. Jeśli Mechagodzilla jest w stanie v i otrzyma instrukcję X, to przechodzi do stanu v_X.

Grupa informatłuków pisze program dla Mechagodzilli. Jest to ciąg m 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.

Pierwszy wiersz wejścia zawiera cztery liczby naturalne n, k, m, z (1 ≤ n ≤ 100, 1 ≤ k ≤ n, 1 ≤ m ≤ 1 000 000, 1 ≤ z ≤ 50 000), 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 k liczb naturalnych b_i (1 ≤ b_i ≤ n), które oznaczają numery stanów bojowych. Stan o numerze 1 to stan początkowy.

Następne n wierszy zawiera po 26 liczb naturalnych i_X (1 ≤ i_X ≤ n), oznaczających, że jeśli Mechagodzilla będzie w stanie i i dostanie instrukcję X, to przejdzie do stanu i_X.

Następny wiersz zawiera napis złożony z m wielkich liter alfabetu angielskiego, oznaczających program dla Mechagodzilli.

Następne z wierszy zawiera po dwie liczby naturalne a_i, b_i (1 ≤ a_i, b_i ≤ m), oznaczające kolejne poprawki informatłuków. Każda taka poprawka oznacza, że instrukcje na pozycjach a_i i b_i zamieniają się miejscami.

Na wyjściu należy wypisać z wierszy. Są to odpowiedzi na pytania, czy po kolejnych poprawkach program jest dobry (TAK jeśli tak, NIE w przeciwnym wypadku).