메카고질라

당신이 사는 하부 바이트티아(Lower Byteotia) 지역의 당국은, 케이블을 먹어 치우는 고질라에 맞서 단호하게 대응하기로 결정했다. 고질라와 싸우기 위해 그들은 자신들이 직접 조종할 수 있는 로봇, 메카고질라를 투입했다.

메카고질라는 $n$개의 상태 중 하나에 있을 수 있으며, 그중 하나는 시작 상태이고 일부 상태들은 전투 상태이다. 각 상태에서 메카고질라는 26개의 명령(A부터 Z까지의 대문자로 표시) 중 하나를 실행할 수 있고, 명령을 받으면 다른 상태로 이동한다. 메카고질라가 상태 $v$에 있을 때 명령 $X$를 받으면 상태 $v_X$로 이동한다.

메카고질라를 위한 프로그램은 $m$개의 명령으로 이루어진 문자열이며, 메카고질라는 시작 상태에서 출발해 이 명령들을 순서대로 하나씩 실행한다. 프로그램을 모두 실행한 뒤 메카고질라가 전투 상태에 있으면, 그 프로그램을 좋은 프로그램이라고 부른다.

프로그래머들은 수시로 프로그램의 두 위치에 있는 명령을 서로 맞바꾸는 수정을 한다. 각 수정이 적용될 때마다(수정은 누적된다) 그 시점의 프로그램이 좋은지 판정하라.

첫째 줄에 네 자연수 $n$, $k$, $m$, $z$ ($1 \le n \le 100$, $1 \le k \le n$, $1 \le m \le 10^6$, $1 \le z \le 5 \cdot 10^4$)가 주어진다. 각각 상태의 개수, 전투 상태의 개수, 프로그램의 길이, 수정의 횟수를 뜻한다.

둘째 줄에 $k$개의 자연수 $b_i$ ($1 \le b_i \le n$)가 주어지며, 전투 상태들의 번호이다. 번호가 $1$인 상태가 시작 상태이다.

다음 $n$개의 줄에는 각 줄마다 26개의 자연수 $i_X$ ($1 \le i_X \le n$)가 주어진다. $i$번째 줄의 $X$번째 수는, 메카고질라가 상태 $i$에서 명령 $X$(줄의 첫 번째 수가 A, 마지막 수가 Z에 해당)를 받으면 상태 $i_X$로 이동함을 뜻한다.

다음 줄에는 $m$개의 영어 대문자로 이루어진 문자열, 즉 메카고질라를 위한 프로그램이 주어진다.

다음 $z$개의 줄에는 각 줄마다 두 자연수 $a_i$, $b_i$ ($1 \le a_i, b_i \le m$)가 주어진다. 각 수정은 프로그램에서 위치 $a_i$와 위치 $b_i$에 있는 명령을 서로 맞바꾼다는 뜻이다.

$z$개의 줄을 출력한다. 각 줄은 수정이 순서대로 적용된 뒤 프로그램이 좋은지에 대한 답으로, 좋으면 TAK, 그렇지 않으면 NIE를 출력한다.