#include <iostream>
#include <fstream>
using namespace std;
ifstream F("permutari.in");
ofstream G("permutari.out");
int n,x[10],f[10],S[10];

void afisare()
{
    for(int i = 1 ; i <= n ; i++)
        G<<x[i]<<' ';
    G<<'\n';
}

void afisare1()
{
    for(int i = 1 ; i <= n ; i++)
        cout<<x[i]<<' ';
    cout<<'\n';
    for(int i = 1 ; i <= n ; i++)
        cout<<S[i]<<' ';
    cout<<'\n';
    for(int i = 1 ; i <= n ; i++)
        cout<<f[i]<<' ';
    cout<<'\n';
    cout<<'\n';
}

bool conditie(int k)
{
    if( f[x[k]] == 0 )
        return true;
    return false;

}

void BKT(int k)
{
    int l;
    if( k == n+1 )
        afisare();
    else
        for(l = 1 ; l <= n ; l++)
        {
            x[k] = l;
            if( conditie(k) == true )
            {
                f[x[k]] = 1;
                BKT(k+1);
                f[x[k]] = 0;
            }
        }
}

void BKT1()
{
    int i,ok,k=1;
    for( i = 1 ; i <= n ; i++)
        S[i] = 1;
    while( k > 0 )
    {
        if( k == n+1 )
        {
            afisare();
            k--;
            f[x[k]] = 0;
              x[k] = 0;
        }
        else
        {
            ok = 0;
            for( i = S[k] ; i <= n ; i++)
            {
                S[k] = i+1;
                x[k] = i;
                if( conditie(k) == true )
                {
                    f[x[k]] = 1;
                    k++;
                    ok=1;
                    break;
                }
                //else x[k] = 0;
            }
            if( ok == 0 )
            {
                S[k] = 1;
                k--;
                f[x[k]] = 0;
                x[k] = 0;
            }
        }
        //cout<<"ok:"<<ok<<" k = "<<k<<'\n';afisare1();
    }
}

int main()
{
    F>>n;
    F.close();
    BKT1();
    //BKT(1);
    G.close();
    return 0;
}