Cerința

Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale ordonate strict crescător astfel încât oricare dintre doi termeni consecutivi ai sumei să aibă parități diferite.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran pe fiecare linie câte un șir de numere naturale ordonate strict crescător, separate prin câte un spațiu. Suma numerelor din fiecare șir este n, iar oricare dintre doi termeni consecutivi ai sumei au parități diferite. Șirurile vor fi afișate în ordine lexicografică.

Restricții și precizări

• 1 ≤ n ≤ 150

Exemplu:

Intrare

12

Ieșire

1 2 3 6
1 2 9
1 4 7
3 4 5
12