시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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 vX.

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 ≤ kn, 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 bi (1 ≤ bi ≤ 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 iX (1 ≤ iXn), oznaczających, że jeśli Mechagodzilla będzie w stanie i i dostanie instrukcję X, to przejdzie do stanu iX.

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 ai, bi (1 ≤ ai, bi ≤ m), oznaczające kolejne poprawki informatłuków. Każda taka poprawka oznacza, że instrukcje na pozycjach ai i bi 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).

예제 입력 1

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

예제 출력 1

NIE
TAK