Welcome to the 22nd Annual Minecraft Hunger Games. Your duty is to take Ozi from the starting point to Sinanto waiting at the target point. Let us begin!

This year's game will be held in the top secret island Z-10, just like previous years. Ozi starts from point B and needs to reach point E, where Sinanto is waiting for him. However, it is going to be really long and exhausting. In the island there are mountains and lakes he cannot pass through. Also, Ozi's food supply is limited. You need to find the path with the minimum distance which also passes through at least \(\mathbf{k}\) food resources.

Input

The input consists of several lines. The first line contains \(\mathbf{m}\), \(\mathbf{n}\) and \(\mathbf{k}\). Then you will be given a map with \(\mathbf{m}\) rows and \(\mathbf{n}\) columns. - represent sea or lakes, ^ represents mountains and * represents lands. Point B is the starting point, point E is the target point. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 interval is reserved for food resources.

Output

Output should indicate Ozi's path with characters 'N', 'S', 'E' and 'W' representing north, east, south and west respectively.

Constraints

• \(1 <= \mathbf{m} <= 20\)
• \(2 <= \mathbf{n} <= 20\)
• \(0 <= \mathbf{k} <= 10\)

Example

Input:

15 20 3
--------------------
-------------*------
-*********--*******-
-*****E-***********-
-*******-*-********-
-****1*********-***-
-2*-*******-*******-
-**-*************B*-
-*-******-**-***-**-
-*************0****-
-***-*******-******-
-**-**--***********-
--------*****-------
---------****-------
---------*-**-------

Output:

SSWWWWWWWWWWWWWWWWNNNNEEEEENN

Notes

• There may be multiple correct answers.
• The order of visiting food resources is not important. All food resources are identical so which ones are visited is also not important as long as \(\mathbf{k}\) of them are visited.
• Ozi can only move in the 4 given directions.
• Food resources or your starting point will not block your movement. Visiting the same food resource twice will still count as one resource visited.
• The number food resources in the input is always >= \(\mathbf{k}\).
• All the land is connected to one island. There are no separate islands.
• The map does not necessarily include mountains or sea.