Gonzàlez the Xava's Treasure P51948

(For your mental sanity, you may consider jumping to the Input section.)

Sitting in the backseat of the same car you had been in so many times as a kid, you look through the window and lose your gaze past the rows of trees moving back on both sides. You focus back when you go under the stone arches that delimit your late aunt’s estate. After the car stops in front of Saint Felix Manor’s entrance, you step out and raise your eyes to read the family motto engraved above the door, under the family crest: Felix qui osculat clunes leaenae.

You start to make a shy movement with your arm and, after the man nods his head in approval, you extend your hand to grab and lift one of them and, holding the pastry from both ends, you bend it to make the century-old layers of dough break out of stiffness. Tiny floury flakes fill the air while the miraculously preserved custard starts oozing out of the fracture. You pull out the secret hidden inside the xuixo that only a Montilivi would know: a small rolled-up piece of paper which you leave on the table.

You repeat the gesture two more times with the remaining xuixos and unroll the three fragments. Apparently, they only contain disconnected strokes. But then, with a grave gesture, you stack them one on top of another and lift them in the direction of the stained window through which light enters the room. And there you see it: from the overlapping of the strokes, you can read the exact coordinates in the Onyar river where you will find the wreck of the Cocollona, your ancestor’s galleon where he killed the fearsome pirate Gonzàlez the Xava and where his vast treasure sleeps after the detonations placed by Gonzàlez before his death sank the ship.

These coordinates, illuminated by pink, and yellow, and blue light from the multi-coloured glass, are now your chance to restore the your family’s honour. Can you find where glory awaits for you among the remains of the Cocollona?

Input

Input consists of several cases. Every case starts with the name of the ship, consisting of between 3 and 30 uppercase letters, and the contents of three papers. Each paper i starts and ends with a border line consisting of W_i dashes delimited by a starting and ending ‘+’ char. Then come H_i lines containing the paper contents, which are W_i uppercase letters or digits for printed content, or dots for empty positions. These lines are delimited by starting and ending vertical bars. Assume 1 ≤ W_i, H_i ≤ 50.

The large private test cases have been generated at random. A “reasonable” solution should be fast enough.

Output

Print a line for each test case, with the latitude and longitude where the shipwreck can be found, as digits followed by ‘N’ or ‘S’ for the latitude and ‘E’ or ‘W’ for the longitude.

In order to find the location of the ship, the three pieces of paper must be overlaid and shifted on top of another until the letters consisting of the name of the ship are aligned across the three of them. At that point, a sequence of digits followed by ‘N’ or ‘S’ will give the latitude, and one followed by ‘E’ or ‘W’ will give the longitude.

If, by overlapping, two (or more) pieces of paper have different non-empty content at the same position, that position is unreadable and cannot be used to form the name of the ship or its location. However, this fact does not prevent an alignment of papers from being readable elsewhere.

When searching for latitudes and longitudes, skip all leading zeroes. Because no ships will be at zero latitude or longitude, just ignore any “0S”, “0N”, “0W” and “0E” substrings which are not part of a larger number, when dealing with latitudes and longitudes.

Latitude values will be between “90S” and “90N”. Longitude values will be between “179W” and “179E”. An alignment that provides any value outside of these ranges is incorrect and must be discarded, even if other valid values appear. In particular, the values found should not be trimmed to fit into the correct ranges.

For an alignment of papers to be acceptable, the name of the ship must be built from the three pieces of paper. If two (or just one) papers suffice, discard that alignment.

For every given case, there will be exactly one correct alignment of the three papers that will provide the latitude and the longitude. For that alignment, the name of the ship will appear only once.