Thunk and Plunk

Time limit1sMemory limit128 MB

Summary

Given scattered points labeled as hitting water or solid ground, decide whether any solid point is provably surrounded by water under the stated smoothness guarantee.

Level: Medium7 of 10
Topics: Geometry, Graph, BFS
Solved: No attempts yet

Problem

A group of spelunkers has gathered at the top of a deep vertical shaft in a cave. They have enough rope to lower themselves down, but one of them tossed a small stone down the shaft and heard the "plunk" of a stone landing in water. They do not want to descend if the water there is deep, because that would likely mean there is no exit at the bottom of the shaft that avoids swimming, and they are not equipped for cave diving.

They keep dropping stones down the shaft, listening for a "thunk" (a stone hitting solid ground) or a "plunk" (a stone hitting water). They quickly determine that the bottom of the shaft is a mixture of both. If the water-covered area is unbroken, they suspect the water is quite deep, though perhaps surrounded by a solid shelf. But if there are "islands" of solid ground poking out of the water, then the water is probably shallow overall and the shaft may be worth exploring.

Given the locations where the stones were dropped and the sound heard at each, decide whether there is definite evidence of solid ground completely surrounded by water.

Assume that the outer perimeter of the water-covered area is sharply defined (there is no confusion about what is water and what is land) and is "reasonably" smooth: every point of an island lies at least one foot inside the perimeter of the water, and for any two points $A$ and $B$ on the outer perimeter of the water such that the line segment between them does not touch water, the outer shore can extend inward no more than one foot inside line $AB$ .

Input

The input consists of several test cases. Each case begins with a line containing a single integer $N$ , the number of stones dropped, with $3 \le N \le 200$ . A value of $0$ ends the input. The next $N$ lines each contain

x y s

where $x$ and $y$ are floating-point numbers in the range $-100.0 \ldots 100.0$ and $s$ is a single character: T for "thunk" or P for "plunk". The pair $x, y$ gives the coordinates, in feet, of the place where the stone landed. Each test case contains at least two "plunk"s.

Output

For each test case, print a single line. If there is at least one "thunk" point that is definitely completely surrounded by water, print

There must be an island.

otherwise (no such point exists) print

There might not be an island.

Examples3

Example 1

Input

8
0 0 P
1.0 7.0 T
6.0 0 P
0 6.0 P
6.0 6.0 P
2.5 4.0 P
4.0 4.0 T
4.0 2.0 P
8
0 0 P
1.0 7.0 T
6.0 0 P
0 6.0 P
6.0 6.0 P
2.5 4.0 P
5.5 4.0 T
4.0 2.0 P
0

Expected output

There must be an island.
There might not be an island.

Example 2

Input

Expected output

There must be an island.

Example 3

Input

Expected output

There might not be an island.