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 pare.

Date de intrare

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

Date de ieșire

Programul va afișa pe câte linie a ecranului câte un șir de numere naturale pare ordonate crescător, separate prin câte un spațiu. Suma numerelor din fiecare șir este n. Șirurile vor fi afișate în ordine lexicografică.

Dacă nu există nicio modalitate de a-l scrie pe n ca sumă de numere naturale pare se va afișa mesajul imposibil.

Restricții și precizări

• 1 ≤ n ≤ 40

Exemplu

Intrare

10

Ieșire

2 2 2 2 2 
2 2 2 4 
2 2 6 
2 4 4 
2 8 
4 6 
10

#include <fstream>
//#include <iostream>
using namespace std;

int st[1000], n;

ifstream cin("partitiinumar.in");
ofstream cout("partitiinumar.out");

void afisare(int k){
    for(int i=1;i<=k;i++)
        cout << st[i] << " ";
        cout << '\n';
}

void back(int k, int s){
    for(int i=st[k-1] ; i<=n-s ; i=i+2)
    {
        st[k]=i;
        if(s+st[k]<=n)
            if( s+st[k] == n )
                afisare(k);
            else
                back(k+1, s+st[k]);
    }
}
int main(){

    cin>>n;
    if(n%2)
      cout<<"imposibil";
    else
    {st[0]=2;
    back(1,0);}
    return 0;
}