#include <iostream>
using namespace std;

int v[20],n;

int valid(int k);
int solutie(int k);
void afisare(int k);
void BK(int k);

int main()
{
    cin>>n;
    BK(1);
    return 0;
}

void BK(int k)

{   cout<<"k="<<k<<endl;
    int i;
 for(i=v; i<=n; i++)
       {
           v[k]=i;
           if(valid(k))
           {
               if(solutie(k))
                    afisare(k);
               else
                BK(k+1);
           }
        }
}

int valid(int k)
{ int i;
    for(i=1; i<=k-1; i++)
        if(v[i]==v[k])
            return 0;
            return 1;
}

int solutie(int k)
    {
        if(k==n)
            return 1;
            return 0;
    }
void afisare( int k)
{ int i;
    for(i=1; i<=k; i++)
        cout<<v[i]<<" ";
    cout<<endl;
}