#include<bits/stdc++.h>
#define f(i,j,n) for(int i=j;i<=n;i++)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
using namespace std;
void put(unsigned __int128 x){
    if(x>=10)put(x/10);
    putchar(x%10+'0');
}
unsigned __int128 catl[72];
void solve(int l,int r,unsigned __int128 K,signed *p){
    // cout<<l<<" "<<r<<endl;
    // put(K);cout<<endl;
    if(l>r)return;
        // cout<<l<<" "<<r<<"===============\n";
    if(l+1==r){p[l]=1,p[r]=0;return;}
    for(int R=l+1;R<=r;R+=2){
        unsigned __int128 nl=catl[(R-l-1)>>1],nr=catl[(r-R)>>1];
        // put(nl),cout<<",",put(nr),cout<<'\n';
        // put(nl*nr);cout<<'\n';
        // put(K);cout<<'\n';
        if(nl*nr<=K){
            K-=nl*nr;continue;
        }
        p[l]=1,p[R]=0;
        solve(l+1,R-1,K/nr,p);
        solve(R+1,r,K%nr,p);
        return;
    }
}
void to(unsigned __int128 K,int n,signed *p){
    solve(1,n*2,K,p);
}
int sum[160];
int rc[160];
unsigned __int128 rto(int l,int r,signed *p){
    if(l>r)return 0;
    if(l+1==r){return 0;}
    unsigned __int128 K=0;
    for(int R=l,C=l+1;C<=rc[l];R++,C+=2){
        unsigned __int128 nl=catl[R-l],nr=catl[((r-l+1)>>1)-(R-l)-1];
        if(C!=rc[l]){
            K+=nl*nr;continue;
        }
        unsigned __int128 ls=rto(l+1,C-1,p);
        unsigned __int128 rs=rto(C+1,r,p);
        return K+ls*nr+rs;
    }
    return K;
}
signed R[160];
int c;
vector<int> h[71];
void dfs(int k){
    if(k!=1)R[++c]=1;
    int fr=c;
    for(auto v:h[k]){
        dfs(v);
    }
    if(k!=1)R[++c]=0,rc[fr]=c;
    
}
bool bg(int n,signed *p,signed *q){
    f(i,1,2*n)if(p[i]>q[i])return 1;else if(p[i]<q[i])return 0;
    return 1;
}
bool TG=0;
void init(){
    catl[0]=1;
    catl[1]=1;
    f(i,2,69){
        f(j,1,i){
            catl[i]+=catl[j-1]*catl[i-j];
        }
    }
}
signed q[160];
unsigned __int128 encoder(signed n, const signed *p){
    if(!TG)TG=1,init();
    c=0;
    f(i,1,n)h[i].clear();
    f(i,2,n)h[p[i]].push_back(i);
    dfs(1);
    // cout<<":";f(i,1,n*2-2)cout<<R[i]<<" ";;cout<<endl;
    f(i,1,n*2-2)sum[i]=sum[i-1]+R[i];
    return rto(1,(n-1)*2,R);
}

signed ans[180];
bool TT=0;
void decoder(signed n, unsigned __int128 M, signed *p){
    if(!TT)TT=1,init();
    f(i,1,n*2-2)ans[i]=0;
    to(M,n-1,ans);
    // cout<<":";f(i,1,n*2-2)cout<<ans[i]<<" ";;cout<<endl;
    stack<int> s;
    s.push(1);
    int ct=1;
    p[1]=0;
    f(i,1,n*2-2){
        if(ans[i]==1){
            p[++ct]=s.top();
            s.push(ct);
        }else{
            s.pop();
        }
    }
}