Permutacions lletges P80445

En aquest problema, diem que una permutació és $k$-lletja si té exactament $k$ parells de posicions adjacents amb dos nombres consecutius. Donada una $n$, una $k$ i $m$ posicions per a les quals ja s’ha fixat el contingut, escriviu totes les permutacions $k$-lletges de $\{0, \dots, n - 1\}$ amb el contingut fixat.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 1 i 10, seguida d’una $k$ entre 0 i $n - 1$, seguida d’una $m$ entre 0 i $n$, seguida de $m$ parells $i$ $x$, indicant que a la posició $i$ hi ha d’haver una $x$. Suposeu $0 \le i < n$, $0 \le x < n$, que totes les $i$ són diferents, i que totes les $x$ són diferents.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic totes les permutacions $k$-lletges de $\{0, \dots, n - 1\}$ amb les posicions fixades. Escriviu una línia amb 20 asteriscs al final de cada cas.