Jump out of the trap

Time Limit: 1000 ms

Memory Limit: 65536 ms

Description

In a stroke of luck almost beyond imagination, Brother Gao has developed the first time machine in the world! As he was so interested in western history, he was desperate to traverse to the past. After his traversing, he, using his technique from the “future”, soon became a master of a big kingdom. And then, he commanded people to construct a castle for himself.

After the castle was completed, Gao was a little bit disappointed because each room of the castle is too small for him. He was ambitious so that he wished to have his own room larger. But he was also merciful that he didn’t want his people to reconstruct all. So, he commands that people should break a single wall to make two rooms connected. An added condition is that after the wall was moved, the largest possible new room should be made. As the castle is so big and people at that time is so short of ways of measuring area, the people were in the trap. However, they managed to send one representative to you and ask for your help via the time machine. Can you save them out of the trap?

Here is an example:

        1     2      3      4      5      6      7
   #############################
 1 #      |      #       |       #      |        |      #
   #####-----#####-----#-----#####-----#  
 2 #     #      |       #      #      #       #     #
   #-----#####-----#####-----#####-----#
 3 #     |       |       #      #       #      #     #  
   #-----#########-----#####-----#-----#
 4 # -> #     |       |        |        |       #       #  
   #############################

# = Wall     -,|  = No wall
-> = Points to the wall to remove to make the largest possible new room


By way of example, this castle sits on a 7 x 4 base. A "room" includes any set of connected "squares" in the floor plan. This floor plan contains five rooms (whose sizes are 9, 7, 3, 1, and 8 in no particular order).
Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall. We ensure that the castle always has at least two rooms and always has a wall that can be removed.

Input

The map is stored in the form of numbers, one number for each module, M numbers on each of N lines to describe the floorplan. The input order corresponds to the numbering in the example diagram above. Each module number tells how many of the four walls exist and is the sum of up to four integers:

  1: wall to the west

  2: wall to the north

  4: wall to the east

  8: wall to the south

Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1.

First comes a single integer t(t<=10), which shows that there are t cases of the input. Then each case include several lines:

Line 1: Two space-separated integers: M and N (M,N<=50)

Line 2..M+1: M x N integers, N per line.

Output

The output should contain two lines:

Line 1: The number of rooms the castle has; the size of the origin largest room; the size of the largest room creatable by removing one wall

Line 2: The single wall to remove to make the largest room possible

Choose the optimal wall to remove from the set of optimal walls by choosing the module farthest to the west (and then, if still tied, farthest to the south). If still tied, choose 'N' before 'E'. Name that wall by naming the module that borders it on either the west or south, along with a direction of N or E giving the location of the wall with respect to the module.

Print a blank line between each case, after the last case included.

Sample Input

1
7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

Sample Output

5 9 16
4 1 E

Hint

Source

HJWAJ

提交代码