Problem B
Cellular Merging

It seems that wireless phone companies are merging all the time. As they merge, they have to unify their existing networks, and they may find that they don’t need to keep all their existing cellular towers. This could happen if the two merging networks have two towers that are close to one another – perhaps only one would really be necessary.

Each company lays out its cellular towers in a regular formation. Different companies may use different layouts, such as squares, diamonds (a square turned 45 degrees), equilateral triangles, and hexagons. The figure below shows the possible layouts. Each intersection of two or more lines indicates a cellular tower location.

We consider only a square area between $(0,0)$ and $(z,z)$. Given this area and cellular layouts for two different companies, determine the distance between the closest pair of towers from two the two different companies within the square (including the edges of the bounding square).

Input

Input consists of up to 1000 company merger descriptions. Each description starts with an line with an integer $0 < z \leq 100$, indicating the boundary width and height. After this are two lines, each giving the layout the cell towers for a company. Each layout is described by its type (‘square’, ‘diamond’, ‘triangle’, or ‘hex’), followed by a location of one of the towers in the network (as an $x~ y$ pair, where both $x$ and $y$ are integers, and $0\leq x,y \leq z$), followed by $1 \leq s \leq z$, an integer representing the spacing between the towers (see the diagram). Input ends when $z$ is zero. The location of the tower in a hexagonal pattern is at the bottom-left of the hexagon.

Output

For each merger description, print the distance between the closest pair of towers (one from each network) that are in the square boundary. The answer should be accurate to within $10^{-3}$ distance units.

10
square 1 1 2
square 2 2 2
20
square 4 7 8
triangle 3 3 10
0

1.41421
3.8928