Funhouse

An amusement park is building a new walk-through funhouse in a large $1000\text{ ft} \times 1000\text{ ft}$ space. The park builds walls that divide the space into rooms. Some walls contain doors, so guests can move between adjacent rooms. Guests come in through marked entrances and leave through marked exits, and they may wander freely — there can be many different routes from the entrances to the exits.

The park wants to install "shakerboards" (moving floors) to surprise guests. To keep them from standing out, a shakerboard always fills an entire room wherever it is installed. The designers want every guest to step on a shakerboard at some point during their visit, but shakerboards are expensive, so the park wants to cover as little floor area as possible.

Given a funhouse design, find the smallest total floor area that must be covered with shakerboards so that every possible route from an entrance to an exit passes through at least one room that has a shakerboard.

Movement rules: a guest enters the room just inside an entrance wall, walks between rooms only through doors, and leaves through an exit wall. A shakerboard placed in a room is experienced by every guest who passes through that room — including the room a guest first enters and the room a guest finally exits through.

The input contains several data sets. Each data set begins with a line containing one integer $n$ ($3 \le n \le 1000$), the number of walls. Each of the next $n$ lines describes one wall in the form

x1 y1 x2 y2 EXDW

where $(x_1, y_1)$ and $(x_2, y_2)$ are the wall's endpoints and the last field is a single capital letter:

• E — an entrance;
• X — an exit;
• D — an interior wall that contains a door;
• W — any wall without a door.

E and X appear only on exterior walls, D appears only on interior walls, and W may appear on either. All coordinates are integers between $0$ and $1000$ inclusive. Walls never touch one another except by sharing endpoints, and every endpoint coincides with the endpoint of another wall. No wall has zero length. Every entrance has at least one route to some exit, and every exit has at least one route from some entrance. The funhouse is a single connected building, and every interior wall is connected — directly or through other walls — to an exterior wall.

The input ends with a line containing a single 0.

For each data set, output on its own line the smallest floor area that must be covered with shakerboards so that every guest experiences one. Print the value with exactly one decimal place, with no extra spaces and no blank lines between answers.