#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 37
#define M 74
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,t,leng,lengs,p[N+1],ls[M+1],rs[M+1],s[N+1],num[N+1][N+1],sz[N+1],tong[N+1],tong2[N+1],length,length2,a[N+1],b[N+1],c[N+1];
bool used[N+1],vis[N+1][N+1];
long long dp[N+1][N+1][N+1],DP[N+1][N+1],DSP[N+1][N+1],delta[N+1];
struct poly
{
	int h,w;
	char c[N+1][N+1];
};
poly zero;
struct perm
{
	int p[N+1];
};
struct triang
{
	int a[N+1],b[N+1],c[N+1];
};
poly get_read()
{
	poly x;
	x.h=read(),x.w=read();
	for (int i=1;i<=x.h;++i)
		for (int j=1;j<=x.w;++j)
			cin>>x.c[i][j];
	return x;
}
void get_write(poly x)
{
	puts("poly");
	printf("%d %d\n",x.h,x.w);
	for (int i=1;i<=x.h;++i)
	{
		for (int j=1;j<=x.w;++j) printf("%c",x.c[i][j]);
		puts("");
	}
	return;
}
long long get_rk(poly x)
{
	int sx=x.h,sy=0,res=0,res2=0;
	long long ans=1;
	length=length2=0;
	while (sx!=0||sy!=x.w)
	{
		if (sx!=0&&x.c[sx][sy+1]=='#') tong[++length]=0,sx--;
		else tong[++length]=1,sy++;
	}
	sx=x.h,sy=0;
	while (sx!=0||sy!=x.w)
	{
		if (sy==x.w||x.c[sx][sy+1]=='.') tong2[++length2]=0,sx--;
		else tong2[++length2]=1,sy++;
	}
	for (int i=1;i<=n+1;++i)
	{
		for (int j=0;j<(tong[i]<<1)+tong2[i];++j) ans+=dp[i][res+(j>>1)][res2+(j&1)];
		res+=tong[i],res2+=tong2[i];
	}
	return ans;
}
poly get_data(long long x)
{
	poly d=zero;
	int sx,sy,res=0,res2=0,l,r,ps=0;
	for (int i=1;i<=n+1;++i)
		for (int j=0;j<4;++j)
		{
			if (x<=dp[i][res+(j>>1)][res2+(j&1)])
			{
				tong[i]=j>>1,tong2[i]=j&1,res+=(j>>1),res2+=(j&1);
				break;
			}
			else x-=dp[i][res+(j>>1)][res2+(j&1)];
		}
	for (int i=1;i<=n+1;++i) d.h+=(!tong[i]),d.w+=tong[i];
	for (int i=1;i<=d.h;++i)
		for (int j=1;j<=d.w;++j)
			d.c[i][j]='.';
	sx=d.h,sy=0;
	while (sx!=0||sy!=d.w)
	{
		++ps;
		if (!tong[ps]) d.c[sx][sy+1]='#',sx--;
		else sy++;
	}
	sx=d.h,sy=ps=0;
	while (sx!=0||sy!=d.w)
	{
		++ps;
		if (!tong2[ps]) d.c[sx][sy]='#',sx--;
		else sy++;
	}
	for (int i=1;i<=d.h;++i)
	{
		l=d.w,r=0;
		for (int j=1;j<=d.w;++j)
			if (d.c[i][j]=='#')
				l=min(l,j),r=max(r,j);
		for (int j=l;j<=r;++j) d.c[i][j]='#';
	}
	return d;
}
perm get_read2()
{
	perm x;
	for (int i=1;i<=n;++i) x.p[i]=read();
	return x;
}
void get_write2(perm x)
{
	puts("perm");
	for (int i=1;i<=n;++i) printf("%d ",x.p[i]);
	puts("");
	return;
}
long long get_rk2(perm x)
{
	int maxn=0,d=0,ds;
	long long ans=1;
	for (int i=1;i<=n;++i) used[i]=0;
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;++j) s[j]=s[j-1]+(!used[j]);
		for (int j=1;j<x.p[i];++j)
			if (!used[j])
			{
				if (maxn>j) ds=max(d,j);
				else ds=d;
			    if (!(s[ds]-(ds>=j))) ans+=DSP[n-i][s[max(maxn,j)]];
			}
		used[x.p[i]]=1;
		if (maxn>x.p[i]) d=max(d,x.p[i]);
		maxn=max(maxn,x.p[i]);
	}
	return ans;
}
perm get_data2(long long x)
{
	perm y;
	int maxn=0,d=0,ds;
    for (int i=1;i<=n;++i) used[i]=0;
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;++j) s[j]=s[j-1]+(!used[j]);
		for (int j=1;j<=n;++j)
			if (!used[j])
			{
				if (maxn>j) ds=max(d,j);
				else ds=d;
				if (!(s[ds]-(ds>=j)))
				{
					if (x<=DSP[n-i][s[max(maxn,j)]])
					{
						y.p[i]=j;
						break;
					}
					else x-=DSP[n-i][s[max(maxn,j)]];
				}
			}
		used[y.p[i]]=1;
		if (maxn>y.p[i]) d=max(d,y.p[i]);
		maxn=max(maxn,y.p[i]);
	}
	return y;
}
triang get_read3()
{
	triang x;
	for (int i=1;i<=n;++i) x.a[i]=read(),x.b[i]=read(),x.c[i]=read();
	return x;
}
void get_write3(triang x)
{
	puts("triang");
	for (int i=1;i<=n;++i) printf("%d %d %d\n",x.a[i],x.b[i],x.c[i]);
	return;
}
void dfs(int x)
{
	if (ls[x]||rs[x]) dfs(ls[x]),dfs(rs[x]),sz[x]=sz[ls[x]]+sz[rs[x]];
	else sz[x]=1;
	return;
}
long long calc(int x)
{
	if (!x) return 0;
	long long res=0;
	for (int i=1;i<sz[ls[x]];++i) res+=delta[i]*delta[sz[x]-i];
	return res+calc(ls[x])*delta[sz[rs[x]]]+calc(rs[x]);
}
long long get_rk3(triang x)
{
	leng=0;
	for (int i=1;i<=n+2;++i)
		for (int j=i+1;j<=n+2;++j)
			vis[i][j]=num[i][j]=0;
	for (int i=1;i<=n;++i) vis[x.a[i]][x.b[i]]=vis[x.b[i]][x.c[i]]=vis[x.a[i]][x.c[i]]=1;
	for (int i=n+2;i>=1;--i)
		for (int j=i+1;j<=n+2;++j)
			if (vis[i][j])
			{
				num[i][j]=++leng,ls[leng]=rs[leng]=0;
				for (int k=i+1;k<=j-1;++k)
					if (vis[i][k]&&vis[k][j])
						ls[num[i][j]]=num[i][k],rs[num[i][j]]=num[k][j];
			}
	dfs(num[1][n+2]);
	return calc(num[1][n+2])+1;
}
int build(int x,long long d)
{
	int nw=++leng;
	ls[nw]=rs[nw]=0;
	if (x==1) return nw;
	for (int i=1;i<=x-1;++i)
	{
		if (d<delta[i]*delta[x-i])
		{
		    ls[nw]=build(i,d/delta[x-i]),rs[nw]=build(x-i,d%delta[x-i]);
			return nw;
		}
		else d-=delta[i]*delta[x-i];
	}
}
void dfs2(int x,int l,int r)
{
	vis[l][r]=1;
	if (l+1==r) return;
	dfs2(ls[x],l,l+sz[ls[x]]),dfs2(rs[x],l+sz[ls[x]],r);
	return;
}
bool cmp(int x,int y)
{
	if (a[x]!=a[y]) return a[x]<a[y];
	else if (b[x]!=b[y]) return b[x]<b[y];
	else return c[x]<c[y];
}
triang get_data3(long long x)
{
	triang d;
	for (int i=1;i<=n+2;++i)
		for (int j=i+1;j<=n+2;++j)
			vis[i][j]=0;
	leng=lengs=0;
	int nw=build(n+1,x-1);
	dfs(nw),dfs2(nw,1,n+2);
	for (int i=1;i<=n+2;++i)
		for (int j=i+1;j<=n+2;++j)
			if (vis[i][j])
				for (int k=i+1;k<=j-1;++k)
					if (vis[i][k]&&vis[k][j])
						++lengs,p[lengs]=lengs,a[lengs]=i,b[lengs]=k,c[lengs]=j;
	sort(p+1,p+lengs+1,cmp);
	for (int i=1;i<=lengs;++i) d.a[i]=a[p[i]],d.b[i]=b[p[i]],d.c[i]=c[p[i]];
	return d;
}
int main()
{
	string s;
	long long x;
	n=read(),t=read();
	for (int i=0;i<=n+1;++i) dp[n+1][i][i]=1;
	for (int i=n+1;i>=1;--i)
		for (int j=0;j<=i-1;++j)
			for (int k=j+(i!=1);k<=i-1;++k)
				dp[i-1][j][k]=dp[i][j][k]+dp[i][j+1][k]+dp[i][j][k+1]+dp[i][j+1][k+1];
    DP[0][1]=1;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=i;++j)
			for (int k=2;k<=j+1;++k)
				DP[i][k]+=DP[i-1][j];
	for (int i=0;i<=n;++i)
		for (int j=i+1;j>=0;--j)
			DSP[i][j]=DSP[i][j+1]+DP[i][j];
	delta[1]=1;
	for (int i=2;i<=n+1;++i)
		for (int j=1;j<=i-1;++j)
			delta[i]+=delta[j]*delta[i-j];
	while (t--)
	{
		cin>>s;
		if (s=="poly")
		{
			x=get_rk(get_read());
			if (x&1) get_write2(get_data2(x));
			else get_write3(get_data3(x-1));
		}
		else if (s=="perm")
		{
			x=get_rk2(get_read2());
			if (x&1) get_write(get_data(x));
			else get_write3(get_data3(x));
		}
		else
		{
			x=get_rk3(get_read3());
			if (x&1) get_write(get_data(x+1));
			else get_write2(get_data2(x));
		}
	}
	return 0;
}