인장

Bytie는 오늘 우편물에서 이상한 문서를 하나 발견했다. 삼촌 Byteasar가 거액의 유산을 남겼다는 통지서였다. 그 문서에는 Byteotia 왕국의 인장이 여러 번 찍혀 있다. 그래도 혹시 모르니 Bytie는 이것이 사기인지 확인하려 한다. 이를 위해 그는 이것들이 진짜 인장의 날인인지 판별하려 한다.

Bytie는 Byteotia 왕국의 인장이 어떻게 생겼는지 잘 알고 있다. 그런데 받은 문서에는 잉크가 너무 많이 묻어 있어서, 열의가 넘친 서기가 여러 번 찍은 것인지 Bytie를 속이려는 빈약한 시도인지 구분하기 어렵다. 문서에 찍힌 날인들과 Byteotia 왕국 인장의 행렬이 주어질 때, 문서의 날인들이 정당한지 판별하는 프로그램을 작성해 Bytie를 도와라.

Byteotia 왕국의 인장에는 복잡한 보안 장치가 있어서 다음 세 가지가 모두 불가능하다. (1) 인장 날인을 회전시키는 것, (2) 일부가 문서에 나타나지 않는 인장 날인을 만드는 것, (3) 문서의 한 점에 인장을 두 번 이상 찍어 잉크를 묻히는 것.

표준 입력의 첫 줄에는 데이터 세트의 수를 나타내는 정수 q (1 ≤ q ≤ 10)가 하나 주어진다. 이어지는 줄들이 각 데이터 세트를 차례로 설명한다.

한 데이터 세트의 첫 줄에는 네 정수 n, m, a, b (1 ≤ n, m, a, b ≤ 1000)가 하나의 공백으로 구분되어 주어진다.

다음 n개의 줄은 문서에 찍힌 날인들을 설명한다. 각 줄은 . (점) 또는 x로 이루어진 m개의 문자를 담는다. 점은 문서의 해당 위치에 잉크가 없음을, x는 잉크 자국이 있음을 뜻한다.

그다음에는 Byteotia 왕국 인장이 한 번 찍힌 견본 문서가, Bytie가 받은 문서에 쓰인 것과 같은 형식으로 a개의 줄에 걸쳐 주어지며, 각 줄은 . 또는 x로 이루어진 b개의 문자를 담는다. Bytie의 문서와 정당한 인장 행렬 모두 잉크 자국을 포함한다고 가정한다.

전체 점수의 44%에 해당하는 테스트에서는 n, m, a, b ≤ 150이다.

프로그램은 표준 출력에 정확히 q개의 줄을 출력해야 한다. i번째 줄은 i번째 데이터 세트의 답을 담는다.

Bytie가 받은 문서가 정당한 인장으로 찍힌 것일 수 있다면 그 데이터 세트의 답은 TAK(폴란드어로 예) 한 단어여야 한다. 반대로 문서가 위조품이라면 답은 NIE(폴란드어로 아니요) 한 단어여야 한다.