#include<iostream>
using namespace std;

int n ,x[50];
void afisare();
void Back(int k);
int Maxim(int p);
int main()
{
    cin>>n;
    Back(1);
    return 0;
}
void afisare()
{
    int maxim=Maxim(n);
    for(int i=1;i<=maxim;++i)
    {
        cout<<" { ";
        for(int j=1;j<=n;j++)
            if(x[j]==i)
                cout<<j << " ";
        cout<<"}";
    }
    cout<<endl;
}
void Back(int k)
{
    if(k==n+1)
    {
        afisare();
        return ;
    }
    for(int i=1;i<=Maxim(k-1)+1;i++)
    {
        x[k]=i;
        Back(k+1);
    }
}
int Maxim(int p)
{
    int maxim=0;
    for(int i=1;i<=p;i++)
        if(x[i]>maxim)
            maxim=x[i];
    return maxim;
}