Paraules compensades X46137

Considereu una paraula $s$ de longitud $n$, amb només lletres ‘a’ i ‘b’. Per a qualsevol dels seus prefixos $p$, sigui $a(p)$ el nombre de ‘a’ dins de $p$, i sigui $b(p)$ el nombre de ‘b’ dins de $p$. En aquest problema, direm que $s$ està compensada si i només si per a qualsevol dels $n+1$ prefixos $p$ d’$s$ es compleix $\vert a(p) - b(p) \vert \le 2$.

Per exemple, “abbaaabb” està compensada, però “abbaaaab” no ho està, perquè “abbaaaa” n’és un prefix amb cinc ‘a’ i dues ‘b’. Com altres exemples, ni “bbb” ni “bbbbbb” estan compensades.

Donada una $n$, escriviu totes les paraules compensades d’aquesta longitud.

Entrada

L’entrada consisteix en una $n$ entre 1 i 18.

Sortida

Escriviu en ordre alfabètic totes les paraules compensades amb $n$ caràcters escollits entre ‘a’ i ‘b’.