Your task is to regulate traffic on a crossroads. There are 4 roads coming from north, east, south and west.
The input is a string representing the upcoming traffic on each road. For example,
NNNWS indicates there is a total of 5 cars: three at the north, one at the west and one at the south. The order of characters has no importance here,
NNNWS is equivalent to
You must output the order in which the cars should go, using the priority to the right rule: cars coming from the south must let cars coming from east go first, east gives way to north, north gives way to west and west gives way to south.
For example, with the input
NNNWS, the south car should go first, then the west car, then the 3 north cars. The output should thus be
There are some indecidable cases, for example
NNWSE : you should then output the string
N => N NW => WN NWS => SWN SNW => SWN SSSSS => SSSSS ENNNNES => NNNNEES NS => stuck NNWSE => stuck