#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) ((x).begin()), ((x).end())
typedef long long LL;
mt19937 gene(233);
int N = 0;
LL dperm[77][77];
typedef pair<int, int> pii;

#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937_64 mrand(1234); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

namespace subtask1 {

#define mp make_pair
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define SZ(x) ((int)(x).size())
typedef long long ll;
const int N=37;
ll dp[N][N][N];
bool prec;
void precalc() {
	if (prec) return;
	prec=1;
	int n=36;
	for (int i=0;i<n;i++) dp[0][0][i]=1;
	for (int i=1;i<n;i++) {
		for (int l=0;l<n;l++) for (int r=l;r<n;r++) {
			for (int pl=0;pl<n;pl++) for (int pr=pl;pr<n;pr++) if (pl<=l&&pr>=l&&pr<=r)
				dp[i][l][r]+=dp[i-1][pl][pr];
		}
	}
}
ll encode(vector<string> poly) {
	precalc();
	int r=SZ(poly),c=SZ(poly[0]);
	int n=r+c;
	ll ans=0;
	for (int R=1;R<r;R++) {
		int C=n-1-R;
		for (int i=0;i<=C;i++) {
			ans+=dp[R-1][i][C];
		}
	}
	int ql=c-1,qr=c-1;
	for (int i=r-1;i>=0;i--) {
		int p1=c,p2=-1;
		rep(j,0,c) if (poly[r-1-i][j]=='#') p1=min(p1,j),p2=max(p2,j);
		for (int l=0;l<c;l++) for (int r=l;r<c;r++) {
			if (mp(l,r)==mp(p1,p2)) goto fd;
			if (l<=ql&&r>=ql&&r<=qr) {
				ans+=dp[i][l][r];
			}
		}
		fd:;
		ql=p1; qr=p2;
	}
	//printf("%lld\n",ans);
	return ans;
}
vector<string> decode(ll x,int n) {
	precalc();
	int r=0;
	for (int R=1;R<=n;R++) {
		int C=n-R;
		ll s=0;
		for (int i=0;i<=C;i++) s+=dp[R-1][i][C];
		if (x>=s) {
			x-=s;
			r++;
		} else break;
	}
	++r;
	int c=n+1-r;
	vector poly(r,string(c,'.'));
	int ql=c-1,qr=c-1;
	for (int i=r-1;i>=0;i--) {
		int p1=-1,p2=-1;
		for (int l=0;l<c;l++) for (int r=l;r<c;r++) {
			if (l<=ql&&r>=ql&&r<=qr) {
				if (dp[i][l][r]<=x) x-=dp[i][l][r];
				else {
					p1=l;p2=r;
					goto fd;
				}
			}
		}
		fd:;
		assert(p1>=0);
		rep(j,p1,p2+1) poly[r-1-i][j]='#';
		ql=p1; qr=p2;
	}
	//for (int i=0;i<r;i++) {
	//	cerr<<poly[i]<<"\n";
	//}
	return poly;
}

}
#undef mp
LL encodepoly() {
    using namespace subtask1;
    int n, m;
    cin >> n >> m;
    vector<string> vec;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        vec.pb(s);
    }
    return encode(vec);
}

void decodepoly(LL x) {
    using namespace subtask1;
    vector<string> vec = decode(x, ::N);
    printf("poly\n%d %d\n", vec.size(), vec[0].size());
    for(auto t : vec) {
        printf("%s\n", t.c_str());
    }
}

namespace sub3 {

    map<pii, int> mp;
    vector<array<int, 3> > tr;
    vector<vector<int> > e;
    vector<int> q;
    vector<array<int, 3> > decomp;
}
void dfs(int v, int fa) {
    using namespace sub3;
    q.pb(1);
    int ls = -1, rs = -1;
    for(int y : e[v]) {
        if(y == fa) continue;
        int isleft = false;
        for(int d = 0; d < 3; d++) {
            if(tr[y][d] == tr[v][0]) {
                isleft = true;
                int sum = tr[y][0] + tr[y][1] + tr[y][2];
                tr[y][0] = tr[v][0];
                tr[y][1] = tr[v][2];
                tr[y][2] = sum - tr[y][0] - tr[y][1];
                break;
            }
        }
        if(isleft) {
            ls = y;
        }else {
            int sum = tr[y][0] + tr[y][1] + tr[y][2];
            tr[y][0] = tr[v][2];
            tr[y][1] = tr[v][1];
            tr[y][2] = sum - tr[y][0] - tr[y][1];
            rs = y;
        }

    }

    if(ls != -1) {
        dfs(ls, v);
    }
    q.pb(-1);
    if(rs != -1) {
        dfs(rs, v);
    }
}
LL encodetriang() {
    using namespace sub3;
    int n = N + 2;
    int rt = -1;
    mp.clear();
    tr.resize(n - 2);
    e.clear();
    e.resize(n - 2);
    q.clear();
    for(int i = 0; i < n - 2; i++) {
        for(int d = 0; d < 3; d++) {
            scanf("%d", &tr[i][d]);
            tr[i][d]--;
        }
        if(tr[i][0] == 0 && tr[i][1] == 1) {
            rt = i;
        }
        for(int d = 0; d < 3; d++) {
            int x = tr[i][d], y = tr[i][(d + 1) % 3];
            if(x > y) swap(x, y);
            //printf("%d %d\n", x, y);
            pii p{x, y};
            if(mp.count(p)) {
                e[mp[p]].pb(i);
                e[i].pb(mp[p]);
                //printf("%d->%d\n", i, mp[p]);
                mp.erase(p);
            }else {
                mp[p] = i;
            }
        }
    }
    dfs(rt, -1);
    //for(int i = 0; i < 2 * n - 4; i++) {
    //    printf("%c", q[i] == 1 ? '(' : ')');
    //}
    LL res = 0;
    int cur = 0;
    for(int i = 2 * n - 4; i >= 1; i--) {
        if(q[i - 1] == -1) {
            cur++;
        }else {
            res += dperm[i - 1][cur + 1];
            //printf("%d %d %d\n", i - 1, cur + 1, dperm[i - 1][cur + 1]);
            cur--;
        }
        //cout << cur << endl;
    }
    return res;
}
void dec(int le, int ri, int lx, int rx) {
    using namespace sub3;
    //printf("%d %d %d %d\n", le, ri, lx, rx);
    int n = N + 2;
    int pos = -1, cnt = 0;
    for(int i = le; i < ri; i++) {
        cnt += q[i];
        //printf("%d %d\n", q[le], cnt);
        if(cnt == 0) {
            pos = i;
            break;
        }
    }
    int mx = (lx - (pos - le + 1) / 2 + n) % n;
    //printf("%d %d %d\n", lx, rx, mx);
    decomp.pb({lx, rx, mx});
    if(pos - le > 2) {
        dec(le + 1, pos, lx, mx);
    }
    if(pos != ri - 1) {
        dec(pos + 1, ri, mx, rx);
    }
}
void decodetriang(LL x) {
    using namespace sub3;
    int n = N + 2;
    int cur = 0;
    for(int i = 2 * n - 4; i >= 1; i--) {
        //cout << x << ' ' << dperm[i - 1][cur + 1] << endl;
        if(x < dperm[i - 1][cur + 1]) {
            q.push_back(-1);
            cur++;
        }else{
            x -= dperm[i - 1][cur + 1];
            q.push_back(1);
            cur--;
        }
    }
    reverse(all(q));
    //for(int i = 0; i < 2 * n - 4; i++) {
    //    printf("%c", q[i] == 1 ? '(' : ')');
    //}
    decomp.clear();
    dec(0, n * 2 - 4, 0, 1);
    for(int i = 0; i < n - 2; i++) {
        sort(all(decomp[i]));
    }
    sort(all(decomp));
    printf("triang\n");
    for(int i = 0; i < n - 2; i++) {
        printf("%d %d %d\n", 1 + decomp[i][0], 1 + decomp[i][1], 1 + decomp[i][2]);
    }
}
LL encodeperm() {
    int n;
    n = N;
    vector<int> p;
    int mx = -1;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        p.pb(x);
    }
    vector<int> q;
    int cur = 0;
    for(int i = 0; i < n; i++) {
        if(p[i] > mx) {
            int ge = 1;
            for(int j = i + 1; j < n; j++) {
                ge += p[i] > p[j];
            }
            while(cur < ge) {
                q.pb(1);
                cur++;
            }
            mx = p[i];
            q.pb(-1);
            cur--;
        }else {
            q.pb(-1);
            cur--;
        }
    }
    /*for(int i = 0; i < 2 * n; i++) {
        printf("%c", q[i] == 1 ? '(' : ')');
    }*/
    assert(q.size() == n * 2);
    assert(cur == 0);
    LL res = 0;
    for(int i = 2 * n; i >= 1; i--) {
        if(q[i - 1] == -1) {
            cur++;
        }else {
            res += dperm[i - 1][cur + 1];
            //printf("%d %d %d\n", i - 1, cur + 1, dperm[i - 1][cur + 1]);
            cur--;
        }
        //cout << cur << endl;
    }
    N = n;
    return res;
}
void decodeperm(LL x) {
    int cur = 0;
    int n = N;
    vector<int> q;
    for(int i = 2 * n; i >= 1; i--) {
        //cout << x << ' ' << dperm[i - 1][cur + 1] << endl;
        if(x < dperm[i - 1][cur + 1]) {
            q.push_back(-1);
            cur++;
        }else{
            x -= dperm[i - 1][cur + 1];
            q.push_back(1);
            cur--;
        }
    }
    reverse(all(q));
    vector<int> vst(n + 1);
    vector<int> res;
    /*for(int i = 0; i < 2 * n; i++) {
        printf("%c", q[i] == 1 ? '(' : ')');
    }*/
    for(int i = 0, j; i < 2 * n; i = j) {
        int k;
        for(j = i; j < 2 * n && q[j] == 1; j++) {
            cur++;
        }
        int ord = 0;
        for(int l = 1; l <= n; l++) {
            if(!vst[l]) {
                ord++;
                if(ord == cur) {
                    vst[l] = true;
                    res.pb(l);
                    break;
                }
            }
        }
        
        for(k = j; k < 2 * n && q[k] == -1; k++) {
            cur--;
            if(k != j) {
                for(int l = 1; l <= n; l++ ) {
                    if(!vst[l]) {
                        vst[l] = true;
                        res.pb(l);
                        break;
                    }
                }
            }
        }
        j = k;
    }
    printf("perm\n");
    for(int i = 0; i < n; i++) {
        printf("%d%c", res[i], i == n - 1 ? '\n' : ' ');
    }
}
int main() {
    /*LL x = encodepoly();
    cout << x << endl;
    decodepoly(x);
    return 0;*/
    int t;
    cin >> N >> t;
    cout << N << ' ' << t << endl;
    dperm[0][0] = 1;
    for(int i = 0; i <= 2 * N - 1; i++) {
        for(int j = 0; j <= N && j <= i; j++) {
            if(dperm[i][j] != 0) {
                dperm[i + 1][j + 1] += dperm[i][j];
                if(j - 1 >= 0) {
                    dperm[i + 1][j - 1] += dperm[i][j];
                }
            }
        }
    }
    for(int qq = 0; qq <= t; qq++) {
        string tp;
        cin >> tp;
        if(tp == "poly") {
            LL x = encodepoly();
            if(x % 2 == 0) {
                decodeperm(x);
            } else {
                decodetriang(x - 1);
            }
        } else if(tp == "perm") {
            LL x = encodeperm();
            if(x % 2 == 0) {
                decodepoly(x);
            }else {
                decodetriang(x);
            }
        } else if(tp == "triang") {
            LL x = encodetriang();
            if(x % 2 == 0) {
                decodepoly(x + 1);
            }else {
                decodeperm(x);
            }
        }
    }
}