Trong nỗ lực thách thức quan niệm rập khuôn rằng bò là những sinh vật vụng về, Bessie, cô bò quý của Farmer John, đã đăng ký một lớp ba lê nhập môn. Buổi biểu diễn cuối khóa của cô diễn ra vào tuần tới, và FJ muốn giúp cô bằng cách dựng một sân khấu hình chữ nhật đủ lớn để cô có thể thực hiện toàn bộ bài múa mà không bị ngã khỏi mép sân khấu.

Bài múa của Bessie sẽ diễn ra trên một sân khấu hình chữ nhật gồm một lưới các ô vuông \(1 \times 1\). Bốn chân của Bessie được ký hiệu ngắn gọn như sau:

FR: Chân trước bên phải
FL: Chân trước bên trái
RR: Chân sau bên phải
RL: Chân sau bên trái

Ban đầu, bốn chân của cô nằm trong 4 ô kề nhau tạo thành một hình vuông như sau, với Bessie quay mặt về hướng bắc:

FL FR
RL RR

Bài múa của Bessie tuân theo một chuỗi gồm \(N\) chỉ dẫn (\(1 \le N \le 1000\)), mỗi chỉ dẫn yêu cầu cô di chuyển một chân sang một ô hoặc xoay 90 độ theo chiều kim đồng hồ.

Chỉ dẫn di chuyển một chân gồm 3 ký tự: hai ký tự đầu xác định chân cần di chuyển, còn ký tự cuối xác định hướng di chuyển (F = tiến, B = lùi, R = sang phải, L = sang trái). Ví dụ, FRF nghĩa là Bessie phải di chuyển chân trước bên phải về phía trước một ô, còn RLR nghĩa là cô phải di chuyển chân sau bên trái sang phải một ô. Tất nhiên, hướng di chuyển được tính tương đối theo hướng mà Bessie đang quay mặt.

Chỉ dẫn xoay cũng gồm 3 ký tự: hai ký tự đầu xác định chân duy nhất mà Bessie giữ cố định và xoay 90 độ theo chiều kim đồng hồ quanh chân đó. Ký tự cuối là P (viết tắt của pivot, tức là xoay). Ví dụ, chỉ dẫn FRP nghĩa là Bessie phải xoay 90 độ theo chiều kim đồng hồ quanh chân trước bên phải đang giữ cố định. Điều này có nghĩa là nếu các chân của cô hiện nằm như sau (với Bessie quay mặt về hướng bắc):

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

thì sau chỉ dẫn FRP, các chân của cô sẽ nằm như sau, với Bessie lúc này quay mặt về hướng đông:

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

Cho \(N\) chỉ dẫn trong bài múa của Bessie, hãy tính diện tích nhỏ nhất của một sân khấu hình chữ nhật cần thiết để chứa các chân của cô trong suốt toàn bộ bài múa.

Nếu Bessie vụng về di chuyển một chân vào cùng ô với một chân khác ở bất kỳ thời điểm nào, cô sẽ vấp ngã và không thể hoàn thành bài múa; trong trường hợp này, hãy in ra -1. Lưu ý rằng đây là trường hợp duy nhất khiến Bessie vấp ngã; sau tất cả quá trình luyện tập, cô đã trở nên khá dẻo dai và có thể dễ dàng đưa chân vào những tư thế khá kỳ lạ (ví dụ, hai chân sau nằm xa về phía trước hơn hai chân trước).

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, từ dòng 2 đến dòng \(1+N\), mỗi dòng chứa một chỉ dẫn gồm 3 ký tự trong bài múa của Bessie.

Dữ liệu ra

• Dòng 1 chứa diện tích nhỏ nhất của một sân khấu hình chữ nhật cần thiết để chứa các chân của Bessie trong suốt toàn bộ bài múa, hoặc -1 nếu Bessie vấp ngã.

Ví dụ

3
FRF
FRP
RLB

16

.. .. .. .. 
.. .. .. .. (quay mặt về hướng bắc)
.. .. FL FR 
.. .. RL RR 

.. .. .. .. 
.. .. .. FR (quay mặt về hướng bắc)
.. .. FL .. 
.. .. RL RR 

.. RL FL .. 
.. RR .. FR (quay mặt về hướng đông)
.. .. .. .. 
.. .. .. .. 

RL .. FL ..
.. RR .. FR (quay mặt về hướng đông)
.. .. .. ..
.. .. .. ..

Nguồn

USACO 2013 US Open, Bronze — Problem 1: Bovine Ballet

Tác giả đề: Brian Dean, 2013.