#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);
}
}
}
}