RedCapeFlyingCat has a walking plan consisting of Q commands, performed in input order. A command d step represents step consecutive unit steps in direction d. The four directions are N (north), S (south), E (east), and W (west). For example, N 2 followed by E 1 represents the step sequence NNE.
The cat thinks walking one step and immediately walking back is ridiculous. In the step sequence, delete any adjacent pair equal to NS, SN, EW, or WE. After each deletion, the steps on either side become adjacent. Keep deleting eligible pairs until none remains. The final sequence is the same regardless of which eligible pair is deleted first. Output this final sequence in the format selected by type.
For example, the commands N 2, E 1, W 1, and S 1 form NNEWS. Deleting EW gives NNS; deleting the newly adjacent NS leaves N. Its output is N when type = 0, or N1 when type = 1. Also, E 3 followed by W 5 leaves WW.
Only adjacent steps cancel: NESW returns to the starting point but remains unchanged.
1 ≤ Q ≤ 500,000.type is either 0 or 1.d is one of N, S, E, and W.1 ≤ step ≤ 1,000,000,000.| Case | Guarantees |
|---|---|
| 1 | type = 0; every step = 1; exactly one pair is removed. |
| 2 | type = 0; every step = 1; no chain cancellation occurs, regardless of the order in which eligible pairs are removed. |
| 3 | type = 0; every step = 1. |
| 4 | type = 0; every step = 1. |
| 5 | type = 1; the sum of all input step values is at most 5,000. |
| 6 | type = 1; no additional restrictions. |
A chain cancellation removes two steps that were not adjacent in the original expanded route but became adjacent after other steps disappeared. In NSENS, the two NS pairs can be removed in either order without a chain cancellation. In NEWSW, only EW can be removed at first; doing so creates the adjacent NS pair, whose removal leaves W. In SEWNE, removing EW similarly creates the adjacent SN pair.
| Input | Output | Why |
|---|---|---|
3 0 |
E |
The adjacent NS pair cancels. |
3 0 |
E |
The adjacent SN pair also cancels. |
5 0 |
E |
EW disappears; then the newly adjacent SN pair cancels. |
4 0 |
NESW |
No adjacent pair points in opposite directions. |
3 1 |
N1E1 |
Two NS pairs cancel. Include the count 1 for each remaining run. |
4 1 |
N1 |
EW cancels, then one NS pair cancels. |
3 1 |
N4 |
All three commands have the same direction, so they form one run of four steps. |
type = 1)Input:
11 1 N 8 N 4 E 5 W 7 S 4 N 1 E 2 W 2 W 6 S 1 E 10
Output:
N12W2S3W6S1E10
The first two commands combine into N12. Next, E 5 and W 7 cancel for five steps, leaving W2. Then S 4 and N 1 leave S3, while E 2 and W 2 cancel completely. The final three commands contribute W6, S1, and E10; none cancels with its neighbor.
Thus the remaining maximal runs, in order, are N12, W2, S3, W6, S1, and E10. Because type = 1, concatenate these runs without spaces to get N12W2S3W6S1E10.
The first line contains two integers Q and type. Each of the next Q lines contains a direction d and a positive integer step:
Q type d step ... d step
First finish all cancellations. Read the remaining individual steps from left to right; this is the final sequence. Print exactly one line in the format selected by type:
type = 0: print the final sequence unchanged, with one direction character per step. For example, a final sequence of three north steps followed by two east steps is NNNEE.type = 1: scan the final sequence from left to right. Put consecutive steps with the same direction in one group; start a new group only when the direction changes. For each group, print its direction immediately followed by its number of steps in decimal without leading zeros. Concatenate the groups in order, with no spaces or separators. Print the number even when it is 1.For example, if the final sequence is NNNEEN, the type = 1 output is N3E2N1: the last N is a separate group. The groups are based on the final sequence, not on input command boundaries. Thus, N 1, N 2, N 1 produce N4 when type = 1. A group's count may exceed the step value of any single command.