Create a program that will help the hero of Jerome K. Jerome's "Three Men in a Boat, to say nothing of the Dog" Harry to get out quickly out of the Hampton Court labyrinth. The maze on the plan looks like a rectangle, which sides are directed from west to east or from north to south (as far as possible, considering the spherical shape of the Earth). The dimensions of the labyrinth in yards (English measure of length, approximately 91.44 cm) along the parallel and the meridian are expressed in positive integers n and m respectively, and its total area m * n does not exceed 10000 (square yards). The entire maze is divided into squares with a side length of 1 yard. Some of the squares are planted with bushes with thorns, that can be only bypassed.

Input

The first line contains two positive integers m and n - the dimensions of the maze in yards. The following m lines of n characters each contain a maze scheme, in which the character " " (space) means a free square of the surface, the character "U" means a square with a bush, a cross (addition sign) "+" is a Harris' starting location. The elements of the 1 - st and m - th lines and 1 - st and n - th columns correspond to the exit from the maze, if they are a space or an addition sign. Movement in the maze is possible in the directions of the cardinal points to an adjacent square free from bushes. Moving north, south, west or east corresponds to movement up, down, left, or right one character on the input diagram.

Output

The first line must contain the smallest number of steps of length 1 yards that Harry must take to get out of the maze.

The second line should contain a description of such a shortest path - steps from the first to the last, where the letter n denotes a step to the north, s to the south, e to the east, w to the west.

If Harry is already at the exit, then the first line must contain only the number 0, and the second line must be empty.

If it is impossible to get out of the maze (we will not discuss how in this case Harry got to the corresponding place in the maze), then the only line should contain only the number -1.