The path to the treasure is set in the form of indications of how many steps you need to go in one of the four directions: north (N), south (S), west (W), east (E). The entire route is written as a string containing a sequence of numbers followed by letters indicating the direction of movement. For example, the string "7N5E2S3E" means "walk 7 paces north, 5 paces east, 2 paces south, 3 paces east". A route can have many move commands, so each such route can be abbreviated.
For example, the previously given route can be shortened to "5N8E". For the given route to the treasure, shorten it to a string of minimum length.
The program receives as input a string consisting of non-negative integers, not exceeding 10
7 each, and one letter (N, S, W, E ) following each
number. There are no other characters (including spaces) in the string except numbers and direction letters. The string length does not exceed 250 characters. It is guaranteed that the initial
and the end point of the route are different.
The program should output a route leading to the same point, written in the same form as in the input, using the minimum number of characters. If answers
several, the program should display one (any) of them.
| Input |
Output |
Note |
| 7N5E2S3E |
5N8E |
The correct answer would also be "8E5N" |
| 10N30W20N |
30N30W |
The correct answer would also be "30W30N" |