Чтобы сломать стереотипное представление о коровах как о неловких созданиях, корова Беси пошла на балетные курсы. Ее финальное представление состоится на следующей неделе, и ФД хочет помочь ей, построив прямоугольную сцену, достаточную для всего ее представления.
Танец выполняется на прямоугольной сцене, состоящей из квадратных ячеек размером 1 х 1. Ноги Беси описываются следующим образом:
FR: передняя правая нога FL: передняя левая нога RR: задняя правая нога RL: задняя левая нога
В начале танца все 4 ноги находятся в соседних ячейках и формируют квадрат как показано ниже, причем Беси смотрит на север.
FL FR RL RR
Танец Беси - это последовательность из N инструкций (1 <= N <= 1000), где каждая инструкция предписывает либо переместить одну ногу на одну ячейку, или повернуться на 90 градусов по часовой стрелке.
Инструкции переместить ногу состоят из 3 символов, первые два описывают какую ногу перемещать, а последний символ указывает направление движения (F = вперед, B = назад, R = вправо, L = влево). Например, FRF означает переместить правую ногу вперед на одну ячейку, а RLR - означает переместить заднюю левую ногу вправо. Конечно направление движения относительно того направления, куда сориентирована Беси.
Инструкция на поворот также состоит из 3 символов, первые два указывают единственную ногу Беси, которая останется в той же клетке где была и вокруг которой она повернется на 90 градусов по часовой стрелке. В этом случае последний символ - P (поворот). Например, инструкция "FRP" означает, что Беси должна повернуться на 90 градусов по часовой стрелке вокруг своей стационарной передней правой ноги. Например, если Беси ориентирована на север, и ноги расположены так: .. .. .. .. .. FR .. FL .. .. RL RR
то после инструкции "FRP" ее ноги будут расположены так, а Беси будет ориентирована на восток:
RL FL .. RR .. FR .. .. .. .. .. ..
Вам даны N инструкций танца Беси, вычислите минимальную площадь сцены прямоугольной формы, необходимой для того чтобы ноги Беси находились на ней во время всего танца.
Если Беси шагнет в ту же ячейку, где сейчас находится другая нога, она упадет, и танец закончится, в этом случае выводите -1. Заметим, что это единственный случай, когда Беси упадет. Она хорошо напрактиковалась, и ее ноги могут находиться в самых разных, даже странных комбинациях, например, когда ее задние ноги находятся впереди передних.
PROBLEM NAME: ballet
Формат входных данных
* Строка 1: Цедое число N.
* Строки 2..1+N: Каждая строка содержит одну из 3-символьных инструкций.
Формат выходных данных
* Строка 1: Минимальная площадь прямоугольной сцены, содержащей ноги Беси во время всего танца, или -1, если Беси упадет.
Примечание
Беси нужна сцена 4 x 4, ее ноги будут располагаться так:
.. .. .. .. .. .. .. .. (смотрит на север) .. .. FL FR .. .. RL RR
After FRF:
.. .. .. .. .. .. .. FR (смотрит на север) .. .. FL .. .. .. RL RR
After FRP:
.. RL FL .. .. RR .. FR (смотрит на восток) .. .. .. .. .. .. .. ..
After RLB:
RL .. FL .. .. RR .. FR (смотрит на восток) .. .. .. .. .. .. .. ..
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
FRF
FRP
RLB
|
16
|