Hounded by Indecision

Stealing the Duchess's favorite ruby necklace was probably not a good idea. You were making your way toward the city gates when you heard the sound you had been dreading: a sharp whistle, then an answering bark. The constable has fetched his favorite hound and started the search. He might head straight for a gate. He might try to pick up your trail on the way. You really cannot guess. If he reaches the gate before you, you are caught. If he crosses your trail, the hound picks up your scent. The dog already knows your scent, since this is not your first offense. Once there is a trail to follow, the constable looses the hound, who runs fast.

You have a decision to make. If you are absolutely sure that you can reach a gate before the constable and before the hound, you keep the necklace. If you are not sure, you drop the necklace right now into the nearest pile of rubbish and saunter casually away. Even if they grab you, they release you eventually when the necklace is not in your hands.

So, keep the necklace or drop the necklace?

The town is a rectangular maze of discrete squares. A wall that contains one or more exits surrounds it. You know your own position within the town, and you know the location of the kennel where the constable and the hound start out.

1. In each turn (unit of time), you, the constable, and the hound move at the same time.
2. You move zero or one square horizontally or vertically per turn.
3. At the start the constable and the hound move together, also zero or one square horizontally or vertically per turn.
4. When the constable and the hound, moving together, reach a square that you occupied earlier, the hound catches your scent and the constable looses him. From the next turn on, the hound follows your trail at a speed of 1 or 2 squares per turn.
5. If the constable or the hound moves onto the square you occupy, you are caught. To escape, you must reach an exit at least one turn before the constable and before the hound.

The input holds one or more mazes. Each maze begins with a line containing two integers W and H, the width and the height of the maze. The input ends when either of these values is smaller than 3. Neither value is greater than 50.

H lines follow, each containing W characters. The characters mean the following.

1. A space character is an open square.
2. K is an open square holding the kennel, the starting position of the constable and the hound. Every maze holds exactly one.
3. T is an open square holding the original position of the thief, that is you. Every maze holds exactly one.
4. X is a wall.
5. E is an open square that is an exit, a city gate. Every exit lies on the outer perimeter defined by W and H.

Every maze is completely enclosed by X and E characters. There is at least one path between the kennel and you, and there is at least one path between you and each exit.

For each maze, print a single line. If a path exists that guarantees your escape no matter what path the constable and the hound take, print KEEP IT. If no path offers that guarantee, print DROP IT.

In the first maze of the example, the constable and his hound reach, on turn 7, the square where the thief stood on turn 4. The hound is loosed and overtakes the thief on turn 10, or earlier if the thief doubles back.

In the second maze, the thief reaches a city gate in 13 turns, and the constable and the hound hit the trail at that very moment. The thief still gets out of the city before the hound catches him.