# Dora Trip

Nobita is in great trouble. Today he failed to hand in his homework again, so he was heavily punished at school. Learning that, his mother gets furious, and therefore assigns him many tasks to do — to buy vegetables at the market, to collect a parcel at the post office and a lot more. Nobita certainly does not want to see his teacher on his way, nor would he like to meet Jyian, the tough bully. As usual, he asks Doraemon for help. “Oh no!” cried Doraemon. “My everywhere door is broken, and my small pro- pellers have all run out of batteries...” Well, that means Nobita has got to go without Doraemon’s magic tools. “Ah, I still have this. It may well be useful.” From his 4th-dimensional pocket, Doraemon takes out a map of their living area. He then marks on it the places where Nobita has to visit by asterisks (‘’), and where Jyian or his teacher may appear by crosses (‘X’). Now Nobita’s job is simple — he has to find the shortest route, through which he would not visit any of the ’crosses’, and he could finish the maximum number of the jobs (if not all) given by mum. What he needs is just a computer program that works out the path... Imagine that you are Nobita. Write the program. Input The input file contains no more than 20 test cases. The details of each set are given as follows: The first line of each case contains two integers r and c (1 ≤ r, c ≤ 20), which are the number of rows and columns of the map respectively. The next r lines, each with c characters, give the map itself. For each character, a space ‘ ’ stands for an open space; a hash mark ‘#’ stands for an obstructing wall; the capital letter ‘S’ stands for the position of Nobita’s house, which is where his journey is to start and end; the capital letter ‘X’ stands for a dangerous place; and an asterisk ‘’ stands for a place he has to visit. The perimeter of the map is always closed, i.e., there is no way to get out from the coordinate of the ‘S’. The number of places that Nobita has to visit is at most 10. The input file is terminated by a null case where r = c = 0. This case should not be processed. Output For each test case, if Nobita cannot visit any target places at all, just print the line ‘Stay home!’. Otherwise, your program should output the lexicographically smallest shortest path so that the number of target places that Nobita visits is maximized. Use the letters ‘N’, ‘S’, ‘E’ and ‘W’ to denote north, south, east and west respectively. Note that by ‘north’ we mean facing upwards. You can be sure that the length of a correct output path will never exceed 200. Sample Input 55 ##### # S# # XX# # *# ##### 55 #####

2/2 #* X# ###X# #S # ##### 55 ##### #S X# # X# # ## ##### 00 Sample Output WWSSEEWWNNEE EEWW Stay home!