#include<iostream>
#include<vector>
#include<stack>
using namespace std;

int n, cnt;//方案数
vector<int> v;//已出站的列车
stack<int> s;//目前在站中的列车
int state = 1;//还未进站的列车

void dfs(){
    if(cnt > 19) return;
    if(v.size() == n){
        cnt++;
        for(auto a : v) cout << a;
        cout << endl;
        return;
    }

    if(s.size() != 0){
        v.push_back(s.top());
        s.pop();
        dfs();
        s.push(v.back());
        v.pop_back();
    }
    if(state <= n){
        s.push(state);
        state++;
        dfs();
        state--;
        s.pop();
    }
}

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