Bovine Ballet

Farmer John's prize cow Bessie has signed up for an introductory ballet class to challenge the stereotype that cows are awkward. Her final performance is next week, and Farmer John wants to build a rectangular stage large enough that she can perform her entire dance without stepping off the edges.

Bessie dances on a rectangular stage made of a grid of $1 \times 1$ square cells. Her four feet are labeled:

• FR: front right foot
• FL: front left foot
• RR: rear right foot
• RL: rear left foot

The feet start in four adjacent cells forming a square, with Bessie facing north:

FL FR
RL RR

The dance is a sequence of $N$ instructions ($1 \le N \le 1000$). Each instruction either moves one foot by one cell or pivots Bessie 90 degrees clockwise.

A move instruction is 3 characters: the first two name the foot, and the last gives the direction, relative to the way Bessie is currently facing — F (forward), B (back), R (right), or L (left). For example, FRF moves the front right foot one cell forward, and RLR moves the rear left foot one cell to the right.

A pivot instruction is also 3 characters: the first two name the foot that stays planted, and the last is P. Bessie rotates 90 degrees clockwise about that stationary foot, and her facing direction advances 90 degrees clockwise. For example, if her feet are arranged as follows (facing north)

.. .. ..
.. .. FR
.. FL ..
.. RL RR

then after the instruction FRP her feet are arranged like this, with Bessie now facing east:

RL FL ..
RR .. FR
.. .. ..
.. .. ..

Given the $N$ instructions, compute the minimum area of a rectangular stage that can contain all of Bessie's feet throughout the entire dance — this includes the starting position and the position after every instruction.

If Bessie ever moves one foot onto a cell already occupied by another foot, she trips and cannot finish; in that case output -1. This is the only way she trips: she has become very flexible and can place her feet in strange configurations (for instance, with her rear feet farther forward than her front feet). A pivot never causes a trip.

• Line 1: the integer $N$.
• Lines 2 to $N+1$: each line contains one 3-character instruction of Bessie's dance.

• One line: the minimum area of a rectangular stage that can contain Bessie's feet throughout the dance, or -1 if she trips.

In the sample dance, Bessie performs "front right foot forward" (FRF), then "front right foot pivot" (FRP), then "rear left foot back" (RLB). She needs a $4 \times 4$ stage. Her feet move as follows.

Start (facing north):

.. .. .. ..
.. .. .. ..
.. .. FL FR
.. .. RL RR

After FRF (facing north):

.. .. .. ..
.. .. .. FR
.. .. FL ..
.. .. RL RR

After FRP (facing east):

.. RL FL ..
.. RR .. FR
.. .. .. ..
.. .. .. ..

After RLB (facing east):

RL .. FL ..
.. RR .. FR
.. .. .. ..
.. .. .. ..