Autumn 2243. States in the past, the main territorial entity is autonomy. As a result of terraforming, the territory of former Eurasia is now a rectangle, it is divided into w × h square autonomies, which are organized in a grid of w autonomies in width and h in height. Some autonomies are part of the Commonwealth of Crypto, they are crypto-anarchist technocratic societies and do not recognize bureaucracy. The remaining autonomies are part of the Burro confederation, the bureaucracy in them has been brought to the highest perfection.
To move between autonomies, you need a passport. When entering the autonomy of the Crypto community, it is not necessary to present documents, but when entering the autonomy of the Burro confederation, the border service checks the document, fills out special forms and affixes a stamp of its autonomy to the traveler's passport. One stamp occupies one page of the passport, different stamps are placed on different pages.
An experienced traveler named Benjamin wants to get a new passport. To do this ahead of schedule, he needs to fill out all the pages of his old passport with border stamps. At the moment, he has n empty pages left, so he needs exactly n times to enter the autonomy of Burro. He wants to do it as soon as possible. Benjamin travels in such a way that in one day he moves from the autonomy in which he is located to the autonomy that has a common side with it. Help Veniamin plan his trip in such a way as to fill in all the remaining pages of his passport and at the same time make as few transfers between autonomies as possible.
Benjamin begins his journey in his native autonomy, which belongs to the Commonwealth of Crypto, and can end his journey in any autonomy.
Input data format
The first line of the input file contains three integers: w, h and n (1 ≤ w, h ≤ 500, 1 ≤ n ≤ 1000). Each of the next h lines contains w characters, they define the map of Eurasia. Symbol "A" denotes the autonomy of the Commonwealth of Crypto, and "T" — the autonomy of the Burro confederation. The autonomy in which Benjamin begins his journey is indicated by the symbol "V". The map is given from north to south in rows and from west to east in columns, so the first character of the second line of the input file describes the northwesternmost autonomy. It is guaranteed that there is at least one Burro autonomy in Eurasia.
Output data format
In the output file, output one line of characters "N", "E", "S", "W" — Benjamin's travel plan. These symbols mean that Benjamin should travel north, east, south, or west, respectively. The number of movements in the plan must be minimized; during the journey, Veniamin must enter the Burro autonomy exactly n times. If there are several possible optimal travel plans, you can print any one.
|
Enter |
Output |
5 3 6
AAATA
VAATA
AAAAT |
EEENSSN |
3 1 2
TVT |
WEE |