Folding the Map

On a hiking trail you meet a badly rattled tourist. Her husband gave her a brand new map, and once she opened it she could not fold it back up. You decide to help her.

The map is made of $n \times m$ unit squares. A unit square is the smallest piece, and it cannot be folded any further.

Between every two neighbouring unit squares there is one crease, and each crease is either convex or concave. The map can be folded along the vertical and horizontal lines that run between unit squares, provided that two conditions hold.

First, all creases lying on that line must be of the same kind. Second, creases that come into contact after the fold have to match each other, that is, they have to be of opposite kinds before the fold is made.

Decide whether the map can be folded down to the size of one unit square.

The first line contains the height $n$ and the width $m$ of the map ($2 \le n, m \le 1000$). A unit square measures $1 \times 1$.

The next $n$ lines describe the creases between horizontally neighbouring unit squares. The $i$-th of them contains $m - 1$ characters ^ (a convex crease) or v (a concave crease) with no spaces, listing the creases in the $i$-th row of unit squares from left to right.

The next $n - 1$ lines describe the creases between vertically neighbouring unit squares. The $i$-th of them contains $m$ characters ^ or v, listing the creases between the $i$-th and the $i + 1$-st row of unit squares from left to right.

Print TAK on the first line if the map can be folded down to one unit square, and NIE if it cannot.

Bold edges are concave creases and thin edges are convex ones. The picture shows the map from the sample input.