소의 발레

소가 어색한 동물이라는 통념에 도전하기 위해, Farmer John의 자랑스러운 소 Bessie가 발레 입문 수업에 등록했습니다. 다음 주에 마지막 공연이 있어서, Farmer John은 Bessie가 무대 밖으로 떨어지지 않고 춤 전체를 출 수 있을 만큼 충분히 큰 직사각형 무대를 만들어 주려고 합니다.

Bessie는 $1 \times 1$ 정사각형 칸으로 이루어진 격자 형태의 직사각형 무대 위에서 춤을 춥니다. 네 발은 다음과 같이 이름 붙입니다.

• FR: 앞 오른발
• FL: 앞 왼발
• RR: 뒤 오른발
• RL: 뒤 왼발

처음에 네 발은 서로 붙어 정사각형을 이루며, Bessie는 북쪽을 향합니다.

FL FR
RL RR

춤은 $N$개의 명령으로 이루어집니다 ($1 \le N \le 1000$). 각 명령은 한 발을 한 칸 옮기거나, Bessie를 시계 방향으로 90도 회전시킵니다.

이동 명령은 3글자입니다. 앞 두 글자는 옮길 발을, 마지막 글자는 Bessie가 현재 향한 방향을 기준으로 한 이동 방향을 나타냅니다 — F(앞), B(뒤), R(오른쪽), L(왼쪽). 예를 들어 FRF는 앞 오른발을 앞으로 한 칸, RLR은 뒤 왼발을 오른쪽으로 한 칸 옮깁니다.

회전 명령도 3글자입니다. 앞 두 글자는 바닥에 고정하는 발을, 마지막 글자는 P입니다. Bessie는 그 고정된 발을 중심으로 시계 방향으로 90도 회전하며, 향하는 방향도 시계 방향으로 90도 바뀝니다. 예를 들어 발이 아래와 같이 놓여 있고 (북쪽을 향함)

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

FRP 명령을 수행하면, Bessie는 이제 동쪽을 향하고 발은 다음과 같이 놓입니다.

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

$N$개의 명령이 주어질 때, 춤이 진행되는 내내 Bessie의 모든 발을 담을 수 있는 직사각형 무대의 최소 넓이를 구하세요. 여기서 "내내"에는 시작 위치와 각 명령 이후의 위치가 모두 포함됩니다.

만약 Bessie가 한 발을 다른 발이 이미 있는 칸으로 옮기면, 넘어져서 춤을 끝내지 못합니다. 이 경우 -1을 출력하세요. 넘어지는 경우는 이것뿐입니다. Bessie는 연습을 통해 매우 유연해져서, 뒷발이 앞발보다 더 앞에 오는 등 이상한 자세도 쉽게 취할 수 있습니다. 회전으로는 절대 넘어지지 않습니다.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$째 줄까지: 각 줄에 Bessie의 춤 명령 하나(3글자)가 주어집니다.

• 한 줄: 춤이 진행되는 내내 Bessie의 발을 담을 수 있는 직사각형 무대의 최소 넓이. 넘어지면 -1.

예시 춤에서 Bessie는 "앞 오른발 앞으로"(FRF), "앞 오른발 회전"(FRP), "뒤 왼발 뒤로"(RLB)를 차례로 수행합니다. 이때 $4 \times 4$ 무대가 필요합니다. 발의 이동은 다음과 같습니다.

시작 (북쪽을 향함):

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

FRF 이후 (북쪽을 향함):

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

FRP 이후 (동쪽을 향함):

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

RLB 이후 (동쪽을 향함):

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