#include<bits/stdc++.h>
using namespace std;
#define ull unsigned __int128
const int N=150;

int now,f1,f2;
char s[N];
ull z=1,f[N][N],g[N][N];

void dfs(int x,const int*p,int n)
{
    for(int i=1;i<=n;i++)if(p[i]==x)
    {
        s[now++]='(';
        dfs(i,p,n);
        s[now++]=')';
    }
}

void pre1()
{
    f[0][0]=1;
	for(int i=1;i<N;i++)
    {
		f[i][0]=f[i-1][1];
		for(int j=1;j<N;j++)f[i][j]=f[i-1][j-1]+f[i-1][j+1];
    }
}

void pre2()
{
    g[0][0]=1;
	for(int i=1;i<N;i++)
    {
		g[i][0]=g[i-1][1];
		for(int j=1;j<N;j++)g[i][j]=g[i-1][j-1]+g[i-1][j+1];
    }
}

ull encoder(int n, const int *p)
{
    now=0;
    if(!f1)f1=1,pre1();
    dfs(1,p,n);
    ull rk=0;int num=0;
    for(int i=0;i<now;i++)
    {
        if(s[i]==')')rk+=f[now-i-1][num+1],num--;
        else num++;
    }
    return rk+1;
}

char t[N];

void decoder(int n, ull M, int *p)
{
    if(!f2)pre2(),f2=1;
    int num=0,len=2*n-2;
    for(int i=1;i<=len;i++)
    {
		if(num+1<=(len>>1)&&g[len-i][num+1]>=M) t[i]='(',num++;
		else
        {
			t[i]=')';
			if(num+1<=(len>>1)) M-=g[len-i][num+1];
			num--;
		}
	}
    int cnt=1,now=1;
    for(int i=1;i<=len;i++)
    {
        if(t[i]=='(')
        {
            p[++cnt]=now;now=cnt;
        }
        else now=p[now];
    }
}