Maze

Byteasar read an interesting story not long ago. Its hero was a Greek prince who defeated a monster with a ball of wool. What caught Byteasar was the place where it all happened, a maze. He has been mad about mazes ever since.

Byteasar sketches his mazes on squared paper. Every sketch is a polygon whose sides are the walls of the maze. All sides run parallel to the axes of the coordinate system, and two neighbouring sides always meet at a right angle. Byteasar found out that if the entrance is put on one of the sides, a visitor who keeps a right hand on the wall walks around the whole maze and comes back to the entrance.

The turns made during such a walk can be written down. We write L when the visitor turns left while moving from one wall to the next, and P when the visitor turns right. Byteasar wonders which words over the letters L and P are written down by a walk through some maze.

The first line contains a word of $n$ letters over the letters L and P ($1 \le n \le 100000$). It is the sequence of turns made during one walk around the maze.

Print TAK on the first line if some maze writes down the given word, and NIE otherwise. TAK and NIE are the Polish words for yes and no.

The picture shows a maze that writes down the word LLLLPPLL.