FatMouse and JavaBean

Time Limit: 1 Second    Memory Limit: 32768 KB
Special Judge

FatMouse is lucky enough to find a map of another storehouse which contains his favorite food, JavaBean. The map shows a rectangular house with several square rooms, each either stores some JavaBeans or rests some cats. Each room has at most one door in and at most one door out. Each door opens toward one direction only, that is, room A has a door open toward room B means that one can pass from A to B, but not the other way around (and B can only be reached from A unless FatMouse digs in directly). After some negotiations those cats agree that they can let FatMouse pass if he pays them one JavaBean each. FatMouse can dig into the house and dig out at any point. Now he comes to you with his map, asking if you could tell him where to dig in and where to dig out in order to get the maximum amount of JavaBeans.

Input

Input consists of several test cases.

For each test case, the first line contains 2 positive integers M and N which are the row and column sizes of the house.

Then M lines follow, each contains N pairs of bean_num and door_dir which describe the rooms in the house. The bean_num is the number of JavaBeans stored, or the negative number of cats in that room. The door_dir is a character which represents the door direction of the room where 'E' for east, 'S' for south, 'W' for west, 'N' for north, and 'X' for no door (that is, FatMouse might be able to enter this room from its neighboring rooms, but can only leave this room by digging a hole out).

All the integers in input have their absolute value no more than 500.

Output

For each test case, print in one line the maximum amount of JavaBeans FatMouse can possibly take, followed by two pairs of numbers (x1, y1) and (x2, y2) which are the digging in and out positions, respectively. If there is no way for him to get any JavaBeans at all, print the message "Forget it."

The upper-left corner of the house is (1,1) and the lower-right corner is (M, N).

Please refer to the samples for output format.

Sample Input

1 3
3 E -2 E 3 X
1 1
-1 X

Sample Output

4 (1,1) (1,3)
Forget it.

Submit

Source: ZOJ Monthly, January 2004