Description

Her final recital is next week, so Farmer John (FJ) builds her a rectangular stage.

To keep Bessie from falling off the edge, FJ decides to build a stage that is large enough.

Bessie's dance will occupy a rectangular region composed of many $1 \times 1$ square cells. For convenience, we abbreviate Bessie's four hooves as follows:

• FR: front right hoof (Front right hoof)
• FL: front left hoof (Front left hoof)
• RR: rear right hoof (Rear right hoof)
• RL: rear left hoof (Rear left hoof)

Bessie starts with her hooves occupying four adjacent cells as shown below, initially facing north.

FL FR

RL RR

Bessie's dance consists of $N\ (1 \le N \le 1000)$ instructions. Each instruction either moves one hoof by one cell or rotates $90^\circ$ clockwise.

A move instruction has three characters, where the first two are the hoof code, and the last character is the direction of movement:

• F: forward
• B: backward
• R: right
• L: left

For example, FRF means Bessie's front right hoof moves forward by one cell, and RLR means her rear left hoof moves right by one cell.

Directions are relative to the direction Bessie is currently facing.

Rotation instructions also have $3$ characters. The first two letters are the hoof code and denote the pivot. The last letter is always P (pivot).

For example, FRP means Bessie rotates $90^\circ$ clockwise about her front right hoof.

From the diagram, suppose Bessie's hooves are positioned as follows while she is facing north:

.. .. ..

.. .. FR

.. FL ..

.. RL RR

After executing the instruction FRP, her hooves become:

RL FL ..

RR .. FR

.. .. ..

.. .. ..

and she will be facing east.

Given $N$ dance instructions, compute the minimal rectangular stage area required so that Bessie's hooves never step outside the stage throughout the dance.

If at any time two of her hooves occupy the same cell, she will trip and ruin the performance.

In this case, output $-1$.

However, this is the only reason Bessie would trip, since after practice she is very flexible and can easily perform any unusual moves (for example, extending a hind hoof ahead of a front hoof).

Input Format

The first line contains an integer $N$.

Each of the next $N$ lines contains $3$ uppercase letters describing an instruction.

Output Format

Output a single line with the minimal stage area.

3
FRF
FRP
RLB

16

Hint

Sample explanation:

Bessie's dance requires at least a $4 \times 4$ stage and proceeds as shown:

.. .. .. ..

.. .. .. ..

.. .. FL FR

.. .. RL RR

[Face north]

After FRF:

.. .. .. ..

.. .. .. FR

.. .. FL ..

.. .. RL RR

[Face north]

After FRP:

.. RL FL ..

.. RR .. FR

.. .. .. ..

.. .. .. ..

[Face east]

After RLB:

RL .. FL ..

.. RR .. FR

.. .. .. ..

.. .. .. ..

[Face west]

Translated by ChatGPT 5