산책

바이트오티아(Byteotia)의 마을 이름은 정확히 $n$개의 비트로 이루어진 서로 다른 이진 문자열이다. 이 나라에는 마을이 $2^n - k$개 있으며, 따라서 길이 $n$짜리 비트열 중 정확히 $k$개는 어떤 마을의 이름도 아니다.

일부 마을 쌍은 도로로 직접 연결되어 있다. 구체적으로, 두 마을의 이름이 정확히 한 비트에서만 다를 때, 그리고 그럴 때에만 두 마을은 도로로 직접 이어진다. 도로는 마을 바깥에서 서로 교차하지 않는다.

바이트아사르(Byteasar)는 마을 $x$에서 출발하여 도로만을 따라 마을 $y$까지 산책하려고 한다. 마을 $x$에서 마을 $y$로 이러한 산책이 가능한지 판정하는 프로그램을 작성하여라.

첫째 줄에 두 정수 $n$과 $k$가 공백 하나로 구분되어 주어진다 ($1 \le n \le 60$, $0 \le k \le 1{,}000{,}000$, $k \le 2^n - 1$, $n \cdot k \le 5{,}000{,}000$). $n$은 마을 이름의 비트 길이이고, $k$는 어떤 마을의 이름도 아닌 길이 $n$짜리 비트열의 개수이다.

둘째 줄에는 공백으로 구분된 두 문자열이 주어지며, 각각 0과 1로 이루어진 길이 $n$의 이름이다. 이는 각각 마을 $x$와 $y$의 이름이다.

이어지는 $k$개의 줄에는 어떤 마을의 이름도 아닌 길이 $n$짜리 비트열이 한 줄에 하나씩 주어진다. 각 비트열은 0과 1로 이루어진 길이 $n$의 문자열이다. $x$와 $y$는 이 $k$개의 비트열에 포함되지 않는다.

마을 $x$에서 마을 $y$로 산책이 가능하면 TAK(폴란드어로 '예')를, 불가능하면 NIE(폴란드어로 '아니오')를 한 줄에 출력한다.

예를 들어 $0000$에서 $1011$로 가는 산책은 다음과 같이 두 가지가 가능하다.

• $0000 \to 1000 \to 1100 \to 1110 \to 1111 \to 1011$
• $0000 \to 0100 \to 1100 \to 1110 \to 1111 \to 1011$