Territory

Time limit1sMemory limit1024 MB

Summary

A recorded walk on a grid traces a closed curve; find the largest region enclosed by parts of the path, or 0 if none exists.

Level: Hard8 of 10
Topics: Geometry, Graph, BFS, Implementation
Solved: No attempts yet

Problem

You keep a dog named JOI. JOI's walk repeats moving one step in one of the four cardinal directions. One day you want to measure the size of JOI's territory, so you attach a recording device. The device records one of the four characters N, E, S, W for each one-step move of JOI. When JOI finishes the walk and stops, it records Q, which marks the end of the movement.

Figure 1. An example of JOI's movement (corresponds to the input of Sample 1)

You decide to regard the region enclosed by JOI as JOI's territory. Write a program that finds the area of JOI's territory based on the movement record. The area of a square whose side is one step of JOI is 1. The "region enclosed by JOI" is the figure all of whose sides are part of the path JOI traced during the walk (this figure consists of one or more non-overlapping polygons) with the largest area. If no enclosed region exists, output 0.

Input

Each line contains one character from the five letters N, E, S, W, Q. JOI always moves at least one step. If the character on a line is Q, that line is the last line of the input.

Output

Write the output to standard output. Print only the integer representing the area of the territory.

Examples2

Example 1
Input
```
S
W
W
N
E
E
E
S
E
N
W
Q
```
Expected output
```
3
```
Example 2
Input
```
E
N
E
N
S
W
S
W
S
W
Q
```
Expected output
```
0
```