Find the Shortest Shortcut

Huang Yaoshi, ever mischievous with his daughter Huang Rong, invented a simulation game on Peach Blossom Island. In this game, the island is imagined as an infinite Cartesian plane. Before the game starts, Huang Rong stands at point \(A\) with coordinates given in the input, while her bedroom is located at another point \(B\). Following her father’s commands, she moves step by step in one of the four cardinal directions: north (N), south (S), east (E) or west (W). Each move changes her position by exactly one unit in the respective direction:

\( N: (0, +1),\quad S: (0, -1),\quad E: (+1, 0),\quad W: (-1, 0) \)

Along the journey, Huang Yaoshi asks an intriguing question: Did you take any detours? In other words, was there any portion of the journey where a direct straight‐line move (either horizontal or vertical) could have been taken as a shortcut? A valid shortcut must satisfy the following:

• It spans between two positions on her route, say the positions at steps \(i\) and \(j\) (with \(i < j\)).
• The two positions are aligned either horizontally (same \(y\)-coordinate) or vertically (same \(x\)-coordinate); thus the direct path is a straight line.
• The number of moves actually taken from \(i\) to \(j\) is strictly greater than the minimum number of moves needed if one were to go directly (which is the absolute difference of the non-equal coordinate).

Your task is to help by finding one such shortcut with the smallest possible number of direct moves. The shortcut should be output as a string consisting of repeated characters (all one of N, S, E, or W) representing the direct path from the starting point to the ending point of that segment. If no valid shortcut exists, output 0.

inputFormat

The input consists of three lines:

1. The first line contains two space-separated integers \(S_x\) and \(S_y\), representing the starting coordinates.
2. The second line contains two space-separated integers \(T_x\) and \(T_y\), representing the destination (bedroom) coordinates. It is guaranteed that if you follow the move sequence from \((S_x, S_y)\), you will end up at \((T_x, T_y)\).
3. The third line contains a nonempty string made up exclusively of the characters N, S, E and W. This string represents the sequence of moves taken by Huang Rong.

outputFormat

Output a single line containing the shortcut string. The shortcut string is defined as a sequence of the same character (one of N, S, E or W) that represents the direct straight-line move between two points on the path. If no such shortcut exists, output 0.

sample

0 0
-3 3
NNNENNWWWSSW

NN