Cerința

Se citește un număr natural n (n<16). Afișați în ordine lexicografică toate permutările mulțimii {1,2,…,n} în care elementele pare sunt puncte fixe (nu își schimbă poziția).

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin câte un spaţiu.

Restricții și precizări

• 1 < n < 16

Exemplu:

Intrare

5

Ieșire

1 2 3 4 5 
1 2 5 4 3 
3 2 1 4 5 
3 2 5 4 1 
5 2 1 4 3 
5 2 3 4 1

Explicație

Se vor genera permutările în care 2 și 4 nu își modifică poziția.