지도 접기

등산로에서 잔뜩 당황한 여행자를 만났다. 남편에게 새 지도를 받았는데, 한 번 펼친 뒤로 다시 접지 못하고 있다. 나는 여행자를 돕기로 했다.

지도는 $n \times m$개의 단위 정사각형으로 이루어진다. 단위 정사각형은 더 접을 수 없는 가장 작은 조각이다.

이웃한 두 단위 정사각형 사이에는 접는 선이 하나씩 있고, 각 접는 선은 볼록하거나 오목하다. 지도는 단위 정사각형 사이를 지나는 세로 직선과 가로 직선을 따라 접을 수 있다. 단, 다음 두 조건을 만족해야 한다.

첫째, 그 직선 위에 놓인 접는 선은 모두 같은 종류여야 한다. 둘째, 접은 뒤 서로 맞닿는 접는 선은 서로 어울려야 한다. 즉 접기 전에 서로 반대 종류여야 한다.

지도를 단위 정사각형 하나의 크기로 접을 수 있는지 판정하여라.

첫째 줄에 지도의 높이 $n$과 너비 $m$이 주어진다 ($2 \le n, m \le 1000$). 단위 정사각형의 크기는 $1 \times 1$이다.

다음 $n$개 줄에는 가로로 이웃한 단위 정사각형 사이의 접는 선이 주어진다. 그중 $i$번째 줄에는 ^(볼록한 접는 선) 또는 v(오목한 접는 선) 문자가 공백 없이 $m - 1$개 주어지고, 단위 정사각형 $i$번째 줄에 있는 접는 선을 왼쪽부터 차례로 나타낸다.

이어지는 $n - 1$개 줄에는 세로로 이웃한 단위 정사각형 사이의 접는 선이 주어진다. 그중 $i$번째 줄에는 ^ 또는 v 문자가 $m$개 주어지고, 단위 정사각형 $i$번째 줄과 $i + 1$번째 줄 사이에 있는 접는 선을 왼쪽부터 차례로 나타낸다.

지도를 단위 정사각형 하나의 크기로 접을 수 있으면 첫째 줄에 TAK을, 접을 수 없으면 NIE를 출력한다.

굵은 선은 오목한 접는 선이고, 가는 선은 볼록한 접는 선이다. 예제 입력에 주어진 지도를 그린 그림이다.