Your national space agency has just landed a rover on Mars, and now you are in charge of controlling it.

The rover can move in any of the 4 cardinal directions N, E, S, and W. To instruct the rover to move you can do the following:

• You can send a sequence of moves to be added to the queue. This consists of a string of cardinal directions e.g. NENNESW
• You can send a GO instruction and the rover will execute all the instructions in the queue in order.

There's no direct way to delete moves from the queue if you sent them by accident. However the rover has a special feature: If two consecutive moves have no effect (i.e. would return the rover to the same location) then the rover deletes both of them from the queue. So if you put NNSE in the queue, it would automatically remove NS, NNSE -> NE.

This lets you delete accidental instructions. If you queued NNEESS, but only meant to queue NNE, then no problem, you can queue NNW:

NNEESS NNW
NNEES NW
NNEE W
NNE

So this is all great. However, there was a bit of an issue.

It turns out there's a bug on the rover, and there's no way to patch it now that it's on another planet (you are on Earth in this made up scenario). When you send a sequence to be queued it queues that sequence twice.

So you send E, and it adds EE to the queue. You send NW and it adds NWNW to the queue. If you queue E and then queue NW after it adds EENWNW to the queue.

You take this conundrum to a friend of yours who's an expert in group theory. At first she tells you it's hopeless. However after discussing the problem in detail you mention something you neglected:

At the end of every day the rover always returns to its base camp to charge, transmit data, and receive instructions for the next day. This means all the trips it makes are round trips, always returning to the start location.

At this your friend perks up. "Oh! Well then it's always possible" and she mutters something about the kernel of a finite index free group.

Task

You will take as input a sequence of moves from N, S, E, W. Such that:

• It is "reduced": no direction is adjacent to its opposite (the forbidden substrings are NS, SN, EW, and WE)
• It returns to the origin. That is the total number of Ns is equal to the total number of Ss, and the total number of Es is equal to the total number of Ws.

You will output a list of list of moves, each represents a batch of moves to send to the queue. Your list of moves must be such that if we:

• Double each element of your outer list (e.g. [E, NW, ESW] -> [EE, NWNW, ESWESW])
• Concatenate the results (e.g. [EE, NWNW, ESWESW] -> EENWNWESWESW)
• reduce that result (e.g. EENWNWESWESW -> EENWSW) The result is exactly the input.

Note that there is always a possible output for every input of that form, but outputs are not necessarily unique. That is there are multiple valid solutions to every input, and it doesn't matter which one you give.

This is code-golf, so the goal is to minimize the size of your source code as measured in bytes.

Group theory and proof

I will try to give a concise proof that this is possible using the language of group theory. I will try to keep it at the level it can be understood simply with a background in math and an undergraduate course in group theory.

Group theoretic proof

Let's convert our perspective here a bit:

• N, S, E, W are group elements with concatenation followed by reduction being our product. So E * N = EN. N and S are then inverses (NS = SN = []) and likewise for W and E.
• The group these generate is all reduced sequences, and it is isomorphic to the free group of rank 2, $F_2$.
• The function that takes a sequence of moves and spits out the final coordinate of the rover after taking that path is the "abelianization map" of $F_2$. This is a homomorphism $\operatorname{Ab} : F_2 \rightarrow \mathbb Z^2$.
• The paths we are considering all return to "base camp", location $(0,0)$, so they are maps whose abelianization is $(0,0)$. In group theory we call this the "kernel of $\operatorname{Ab}$", or $\ker(\operatorname{Ab})$. This is a subgroup of $F_2$ also called the "commutator subgroup".
• The moves we are allowed to make are all moves which are comprised of squares, since the rover squares each sequence we send. This is also a subgroup of $F_2$, which we denote $F_2^2$.

Ok, so with that perspective, our goal is to show that $F_2^2$ contains $\ker(\operatorname{Ab})$. That is, every path returning to base camp can be made out of doubled moves.

It turns out that $F_2^2$ is also the kernel of a homomorphism. The natural homomorphism $\eta : F_2\rightarrow \mathbb Z_2^2$ has $F_2^2$ as its kernel. (In general $F_m^n$ is the kernel of the natural map into the Burnside group $B(m,n)$.) There's also a very natural homomorphism $\phi : \mathbb Z^2\rightarrow \mathbb Z_2^2$. And we can convince ourselves that $\phi\circ \operatorname{Ab} = \eta$. So $F_2^2 = \ker(\eta)\supseteq \ker(\operatorname{Ab})$.

So this tells us it is always possible to create the desired path. However it's not very constructive.

Sample algorithm

TODO use the Stallings core graph of $F_2^2$ to give a sample algorithm.

Test cases

TODO