Bạn nuôi một chú chó tên là JOI. Khi đi dạo, mỗi bước JOI di chuyển về một trong bốn hướng bắc, đông, nam hoặc tây. Bạn gắn cho JOI một thiết bị ghi lại mỗi bước bằng ký tự tương ứng N, E, S hoặc W. Khi JOI dừng lại và kết thúc cuộc đi dạo, thiết bị ghi ký tự Q.

Bạn coi phần được đường đi của JOI bao quanh là lãnh thổ của chú chó. Chính xác hơn, đó là hình có diện tích lớn nhất gồm một hoặc nhiều đa giác không chồng lấn, sao cho mọi cạnh của các đa giác đều nằm trên đường JOI đã đi qua. Diện tích của một hình vuông có cạnh bằng một bước chân được tính là \(1\).

Yêu cầu

Cho bản ghi di chuyển, hãy tính diện tích lãnh thổ của JOI. Nếu đường đi không bao quanh phần nào, kết quả là \(0\).

Dữ liệu vào

Đọc từ đầu vào chuẩn. Mỗi dòng chứa đúng một ký tự trong N, E, S, W, Q. Dòng chứa Q là dòng cuối cùng của dữ liệu vào.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên duy nhất là diện tích lãnh thổ.

Ràng buộc

• JOI thực hiện ít nhất một bước di chuyển.
• Tổng số dòng dữ liệu vào, kể cả dòng Q, không vượt quá \(100\,000\).
• Giới hạn thời gian: \(1\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có \(10\) nhóm chấm, mỗi nhóm \(10\) điểm, tổng cộng \(100\) điểm. Để nhận điểm của một nhóm, chương trình phải trả lời đúng tất cả các test trong nhóm. Các mã dưới đây là số hiệu test trong bộ dữ liệu:

Các test tương ứng với \(30\%\) tổng số điểm có không quá \(1000\) dòng dữ liệu vào.

Ví dụ

S
W
W
N
E
E
E
S
E
N
W
Q

3

E
N
E
N
S
W
S
W
S
W
Q

0