Description
RedCapeFlyingCat is planning a walk. The route is written as a string. Each character is one step: N for north, S for south, E for east, and W for west.
RedCapeFlyingCat thinks walking one step and immediately walking back is ridiculous. Whenever two adjacent steps go in opposite directions, the cat removes both from the plan. N and S are opposite; E and W are opposite. Removing a pair may bring another opposite pair together, so continue until no such pair remains.
Cancellation depends on adjacency, not on the final position. For example, NESW returns the cat to its starting point, but no adjacent steps cancel.
Constraints
1 ≤ |s| ≤ 500,000.- At least one step remains after all cancellations.
Additional examples
| Input | Output | Why |
|---|---|---|
NSE |
E |
The adjacent NS pair cancels. |
SNE |
E |
The adjacent SN pair also cancels. |
SEWNE |
E |
EW disappears, then the newly adjacent SN pair cancels. |
NESW |
NESW |
No adjacent pair points in opposite directions. |
Input
The input contains one line with a string s consisting only of N, S, E, and W. Each character represents one step.
Output
Print one line containing the remaining steps