We are at a funfair, where an array of trampolines, named "The Grasshopper Labyrinth", catches our attention. As the gure below shows, all of them are labelled with non-negative integers: \includegraphics{https://static.e-olymp.com/content/9e/9ed66e68399cead2a9e4490d469bc49f27e2dadd.jpg} People are inside, jumping from one trampoline to another, trying to reach the trampoline in the northwest corner, where the exit to the attraction is located. If you reach the exit fast enough, you may win a prize. However, in order to be eligible for the prize, you must abide by the following rule: after leaping from a trampoline labelled with \textbf{z}, you need to get to another one \textbf{z} trampolines away, in the same row or column. Therefore, your problem is to find the shortest path from any trampoline to the way out, measured by the number of leaps needed. Since the length of the jump from any trampoline is given, it is sucient to label each trampoline with the direction of the best jump from it. \includegraphics{https://static.e-olymp.com/content/6e/6e8a1b8472e221a1dbebbc1b08ece5a8badb1155.jpg} For a given starting position, a path is considered shorter than another if it requires a smaller number of jumps; in case of a tie, the path whose rst step gets you northmost in the array is to be preferred; and in case of a tie, the one getting you westmost. Instead of these symbols, we are using the plain text ones: the appropriate cardinal point ('\textbf{N}', '\textbf{S}', '\textbf{E}' or '\textbf{W}') for the arrows, '\textbf{X}' for the trampolines without possible escape, and the asterisk '\textbf{*}' for the special trampoline at the upper left position, which represents the exit. \InputFile Several cases are given in a single test file. The first line in each test case contains a pair of integers between \textbf{1} and \textbf{50}, separated by a single space; the first is the number of rows and the second the number of columns in the matrix. Then, the entries in the matrix follow, line by line, each element being a non-negative integer, again separated by single whitespace characters. A \textbf{0}×\textbf{0} matrix will denote the end of the test cases, and hence should not be analyzed. \OutputFile The expected output of each data case is a character matrix. Each element is one of the allowed charset, "\textbf{N}", "\textbf{S}", "\textbf{E}", "\textbf{W}", "\textbf{X}" or "\textbf{*}", as described above. The output for each case is followed by a blank line.