Do you know Just Odd Inventions Co., Ltd.? The business of this company is doing "just odd inventions." Here we just call it JOI Company.
JOI Company developed new virus "JOI Virus." JOI Company wants to do an experiment by infecting the inhabitants of IOI Island with JOI Virus.
IOI Island takes a rectangular shape. There are parallel roads from east to west and parallel roads from the north to the south. They are separating the island into sections. Each section has just inhabitant living in there. We call the inhabitant living in the section -th from north and -th from west "inhabitant ."
In IOI Island, there are time periods in a day. We call -th time period "time period ." Wind is always blowing from some direction: North, South, East or West. The direction may change depending on the time period. If the time period is the same, wind blows from the same direction independent of the day.
Every inhabitant has a status "resistance." The resistance of inhabitant will be represented by a non-negative integer .
- If equals , it means that inhabitant has high resistance and he or she doesn't get infected with JOI Virus.
- If is a positive integer, it means that inhabitant may get infected with JOI Virus. If the following condition continues for time periods, he or she will get infected from the next time period:
- The inhabitant living in the adjacent section on the direction which wind is blowing from is already infected with JOI Virus.
Note that the last time period of a day and the first time period of the next day is continuous.
With respect to the experiment's purpose, we want to infect at least inhabitant, but we don't want to infect too many inhabitants. At the beginning, we choose inhabitant as the first infected person, and infect him or her with JOI Virus. We can't choose inhabitants with resistance equal to as the first infected person.
Given the direction wind blow from in each time period and the resistance of each inhabitant, write a program which calculates the minimum number of infected inhabitants after days, and the number of the inhabitant who achieves the minimum number when we choose him or her as the first infected person.
Input Specification
Read the following data from the standard input.
is the string with length which denotes the direction wind blow from in IOI Island. consists of kinds of characters N
, S
, W
or E
. The -th character denotes the direction wind blow from in the time period . Note that this is not the direction wind blow toward. N
stands for North, S
stands for South, W
stands for West and E
stands for East.
Output Specification
Write the two lines to the standard output.
The first line should contain the minimum number of the infected inhabitants after days. The second line should contain the number of inhabitants who achieves the minimum number of the infected inhabitants when we choose him or her as the first infected person.
Constraints
- .
- .
- .
- is a string with length , only contains
N
,S
,W
, andE
. - .
- There is at least pair such that .
Subtasks
- (14 points) only contains
W
andE
. - (6 points) , .
- (80 points) There are no additional constraints.
Sample Input 1
6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2
Sample Output 1
8
8
Explanation for Sample 1
Let us consider the condition that we choose inhabitant as the first infected person.
- For inhabitant , during the time period of the day , wind blow from South and the adjacent inhabitant on South is already infected, so he or she will get infected from the time period of the day .
- For inhabitant , during the time period of the day , wind blow from West and the adjacent inhabitant on West is already infected, so he or she will get infected from the time period of the day .
- For inhabitant , during the time period of the day , wind blow from South and the adjacent inhabitant on South is already infected, and during the time period of the day , wind blow from South and the adjacent inhabitant on South is already infected, so he or she will get infected from the time period of the day .
- For inhabitant , during the time period of the day , wind blow from West and the adjacent inhabitant on West is already infected, so he or she will get infected from the time period of the day .
- For inhabitant , during the time period of the day , wind blow from West and the adjacent inhabitant on West is already infected, so he or she will get infected from the time period of the day .
- For inhabitant , during the time period of the day , wind blow from North and the adjacent inhabitant on North is already infected, so he or she will get infected from the time period of the day .
- For inhabitant , during the time period of the day , wind blow from West and the adjacent inhabitant on West is already infected, and during the time period of the day , wind blow from North and the adjacent inhabitant on North is already infected, so he or she will get infected from the time period of the day .
No more inhabitant will be infected with JOI Virus. Hence, when we choose inhabitant as the first infected person, inhabitants will be infected with JOI Virus after days.
Whichever inhabitant we choose as the first infected person, We can't make the number of inhabitants infected with JOI Virus after days less than , so you should output in the first line. If we choose inhabitant , , , , , , or as the first infected person, the number of inhabitants infected after days will be , so you should output in the second line.
Sample Input 2
4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4
Sample Output 2
3
3
This sample input and output satisfies the constraints of Subtask 1.
Comments