Dues files de nombres P83712

Disposeu de $2n$ nombres diferents. Feu un programa que trobi totes les maneres de posar-los en dues files $x_1 \dots x_n$ i $y_1 \dots y_n$ de manera que:

• $x_1 < x_2 < \dots < x_{n-1} < x_n$ ,

• $y_1 < y_2 < \dots < y_{n-1} < y_n$ ,

• per a cada $i$, es compleixi $x_i < y_i$.

Entrada

L’entrada consisteix en $n$, seguit de $2n$ enters diferents. Suposeu $1 \le n \le 11$.

Sortida

Escriviu totes les maneres de posar els nombres complint les condicions demanades. Per a cada manera, escriviu tres línies: les dues files amb les $x_i$ i les $y_i$ separades amb espais, i una línia buida. Escriviu les solucions en ordre lexicogràfic: primer les que tinguin $x_1$ més petita, en cas d’empat les que tinguin $x_2$ més petita, …, en cas d’empat les que tinguin $x_n$ més petita, en cas d’empat les que tinguin $y_1$ més petita, …