바이러스

이진 바이러스 조사 위원회는 0과 1로 이루어진 특정 문자열들이 바이러스 코드임을 알아냈다. 위원회는 모든 바이러스 코드의 집합을 확보했다. 0과 1로 이루어진 어떤 수열이 안전하다(safe)는 것은, 그 수열의 어떤 연속한 부분 수열(연속한 원소들로 이루어진 구간)도 바이러스 코드와 일치하지 않는다는 뜻이다. 위원회는 0과 1로 이루어진 무한하고 안전한 수열이 존재하는지 알고 싶어 한다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 바이러스 코드들을 읽는다.
• 0과 1로 이루어진 무한하고 안전한 수열이 존재하는지 판별한다.
• 결과를 표준 출력에 쓴다.

첫째 줄에 바이러스 코드의 개수를 나타내는 정수 $n$이 주어진다. 이어지는 $n$개의 줄에는 각 줄마다 0과 1로 이루어진 비어 있지 않은 문자열, 즉 하나의 바이러스 코드가 주어진다. 모든 코드의 길이 합은 $30000$을 넘지 않는다.

표준 출력의 첫째 줄이자 유일한 줄에 다음 단어 하나를 출력한다.

• TAK - 0과 1로 이루어진 무한하고 안전한 수열이 존재하는 경우.
• NIE - 그렇지 않은 경우.

코드 집합이 $\{011, 11, 00000\}$일 때, 안전한 무한 수열의 예로 $010101\ldots$ 가 있다. 코드 집합이 $\{01, 11, 00000\}$일 때에는 0과 1로 이루어진 안전한 무한 수열이 존재하지 않는다.