#include <iostream>

using namespace std;
int x[100],n,m;

void afis(int k)
{
    int i;
    cout<<"{";
    for(i=1; i<=k; i++)
        if (x[i]!=0)
        cout<<i<<" ";
    cout<<"}"<<endl;
}
void BT()
{
    int k;
    k=1;
    x[k]=-1;
    while(k>0)
        if(x[k]<1)
        {
            x[k]=x[k]+1;
            if(k==n)
                    afis(k);
                else
                {
                    k++;
                    x[k]=-1;

                }
        }
        else k--;
}


int main()
{
    cin>>n;
    BT();
}