/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

string poly_to_string(vector<vector<char>> &a) {
    int n = isz(a), m = isz(a[0]);
    vector<int> chosen(m);

    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            if (a[i][j] == '#') {
                chosen[j] = i;
                break;
            }
        }
    }

    vector<int> v;
    int ptr = 1;
    for (int j = 0; j < m; ++j) {
        --ptr;
        while (ptr < n and a[ptr][j] == '#') v.emplace_back((++ptr) - chosen[j]);
    }

    int sum = 0;
    string s = "";
    for (int val : v) {
        while (sum > val - 1) {
            s.push_back(')');
            --sum;
        }
        s.push_back('(');
        ++sum;
    }
    while (sum > 0) {
        s.push_back(')');
        --sum;
    }
    return s;
}

string perm_to_string(vector<int> &a) {
    int n = isz(a);

    vector<int> v;
    int maxx = 0, pfx = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < a[i] - maxx; ++j)
            v.emplace_back(++pfx);
        --pfx;
        maxx = max(maxx, a[i]);
    }
    
    int sum = 0;
    string s = "";
    for (int val : v) {
        while (sum > val - 1) {
            s.push_back(')');
            --sum;
        }
        s.push_back('(');
        ++sum;
    }
    while (sum > 0) {
        s.push_back(')');
        --sum;
    }
    return s;
}

string triang_to_string(vector<array<int, 3>> &a) {
    int n = isz(a);

    vector<vector<int>> edges(n + 10);
    map<pair<int, int>, int> mp;
    int root;

    auto cook = [&](int x, int y, int idx) -> void {
        if (x > y) swap(x, y);
        if (x + 1 == y or x + n + 1 == y) {
            // cout << x << " " << y << " = " << idx << endl;
            if (y == 2) root = idx;
            else edges[idx].emplace_back(x != 1 ? -x : -y);
            return;
        }
        // cout << x << " " << y << " " << idx << endl;
        if (mp.find({x, y}) == mp.end()) mp[{x, y}] = idx;
        else {
            int cidx = mp[{x, y}];
            // cout << idx << " <-> " << cidx << endl;
            edges[cidx].emplace_back(idx), edges[idx].emplace_back(cidx);
        }
    };

    for (int i = 0; i < n; ++i) {
        auto [x, y, z] = a[i];
        cook(x, y, i);
        cook(y, z, i);
        cook(z, x, i);
    }

    auto dfs = [&](int v, int p, auto dfs) -> pair<int, string> {
        vector<pair<int, string>> vec;
        for (int u : edges[v]) if (u != p) {
            // cout << v << " -> " << u << endl;
            if (u < 0) vec.emplace_back(u, "");
            else vec.push_back(dfs(u, v, dfs));
        }
        sort(rall(vec));
        assert(isz(vec) == 2);
        if (vec[0].ss.empty() and vec[1].ss.empty()) return {vec[0].ff, "()"};
        if (vec[0].ss.empty()) return {vec[0].ff, "(" + vec[1].ss + ")"};
        if (vec[1].ss.empty()) return {vec[0].ff, vec[0].ss + "()"};
        return {vec[0].ff, vec[0].ss + "(" + vec[1].ss + ")"};
    };

    // cout << root << endl;
    return dfs(root, root, dfs).ss;
}

vector<vector<char>> string_to_poly(string s) {
    int sum = 0;
    vector<int> v;
    for (char ch : s) {
        if (ch == '(') v.emplace_back(++sum);
        else --sum;
    }
    
    sum = 0;
    int x = -1, y = 0;
    vector<pair<int, int>> allpos;
    for (int val : v) {
        if (sum >= val) {
            ++y;
            for (int i = 0; i < val; ++i) {
                // cout << x - i << " " << y << endl;
                allpos.emplace_back(x - i, y);
            }
        }
        else {
            // cout << x + 1 << " " << y << endl;
            allpos.emplace_back(++x, y);
        }
        sum = val;
    }
    int mx, my; tie(mx, my) = *max_element(all(allpos));
    // cout << mx << " " << my << endl;
    vector<vector<char>> res(mx + 1, vector<char>(my + 1, '.'));
    for (auto [x, y] : allpos) res[x][y] = '#';
    return res;
}

vector<int> string_to_perm(string s) {
    set<int> st;
    for (int i = 1; i <= isz(s) / 2; ++i) st.insert(i);

    int sum = 0;
    vector<int> v;
    for (int i = 0; i < isz(s); ++i) {
        if (s[i] == '(') ++sum;
        else {
            if (s[i - 1] == '(') {
                v.emplace_back(sum);
                st.erase(sum);
            }
            else {
                v.emplace_back(*st.begin());
                st.erase(st.begin());
            }
        }
    }

    return v;
}

void sortge(array<int, 3> &a) {
    if (a[0] > a[1]) swap(a[0], a[1]);
    if (a[0] > a[2]) swap(a[0], a[2]);
    if (a[1] > a[2]) swap(a[1], a[2]);
}

vector<array<int, 3>> ar3res;
void dfs(string s, int l, int r, int u, int v) {
    int len = isz(s), sum = 0, pos = -1;
        if (len == 2) {
            array<int, 3> a = {u, v, r};
            sortge(a); ar3res.push_back(a);
            return;
        }
        for (int i = len - 1; i >= 0; --i) {
            sum += (s[i] == ')' ? 1 : -1);
            if (sum == 0) {
                pos = i;
                break;
            }
        }
        if (pos == 0) {
            array<int, 3> a = {u, v, l + 1};
            sortge(a); ar3res.push_back(a);
            dfs(s.substr(1, len - 2), l + 1, r, l + 1, v);
        }
        else if (pos == len - 2) {
            array<int, 3> a = {u, v, r};
            sortge(a); ar3res.push_back(a);
            dfs(s.substr(0, len - 2), l, r - 1, u, r);
        }
        else {
            int inter = l + pos / 2 + 1;
            array<int, 3> a = {u, v, inter};
            sortge(a); ar3res.push_back(a);
            dfs(s.substr(0, pos), l, inter - 1, u, inter);
            dfs(s.substr(pos + 1, len - pos - 2), inter, r, inter, v);
        }
}

vector<array<int, 3>> string_to_triang(string s) {
    ar3res.clear();
    dfs(s, 2, isz(s) / 2 + 2, 2, 1);
    sort(all(ar3res));
    return ar3res;
}

vector<int> brackets_to_sum;

long long dp[100][100];

long long F(int i, int j){
    if(j < 0)return 0;
    if(i == 0)return (j==0);
    if(dp[i][j] != -1)return dp[i][j];
    dp[i][j] = F(i-1, j-1) + F(i-1, j+1);
    return dp[i][j];
}

long long get_order(vector<int> vec){
    long long res = 0, total = 0;
    for(int i = 0; i < vec.size(); i++){
        if(vec[i] == 1)res += F(vec.size() - i - 1, total-1);
        // cout << res << endl;
        total += vec[i];
    }
    return res;
}

vector<int> get_bracket(long long ord, int n){
    vector<int> res;
    int total = 0;
    for(int i = 0; i < n; i++){
        if(!total)res.push_back(1);
        else {
            // cout << F(n-i-1, total-1) << endl;
            if(F(n-i-1, total-1) <= ord){
                ord -= F(n-i-1, total-1);
                res.push_back(1);
            }
            else res.push_back(-1);
        }
        total += res.back();
    }
    return res;
}

string vec_to_string(vector<int> v) {
    string res = "";
    for (int val : v) res.push_back(val == 1 ? '(' : ')');
    return res;
}

vector<int> string_to_vec(string s) {
    vector<int> res;
    for (char ch : s) res.push_back(ch == '(' ? 1 : -1);
    return res;
}

void get(string s, int tp) {
    if (tp == 0) {
        auto a = string_to_poly(s);
        int n = isz(a), m = isz(a[0]);
        cout << "poly\n" << n << " " << m << "\n";
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < m; ++j) cout << a[i][j];
            cout << "\n";
        }
    }
    else if (tp == 1) {
        // cout << s << " " << tp << endl;
        auto a = string_to_perm(s);
        cout << "perm" << "\n";
        for (int val : a) cout << val << " ";
        cout << "\n";
    }
    else {
        auto a = string_to_triang(s);
        cout << "triang" << "\n";
        for (auto [x, y, z] : a) cout << x << " " << y << " " << z << "\n";
    }
}

void xor_1_bracket(string s, int tp) {
    auto vec = string_to_vec(s);
    auto order = get_order(vec) ^ 1;
    auto nvec = get_bracket(order, vec.size());
    s = vec_to_string(nvec);
    if (order & 1) tp = (tp + 1) % 3;
    else tp = (tp + 2) % 3;
    get(s, tp);
}

string s;
int N, n, m, q;
// vector<int> a;
vector<array<int, 3>> a;
// vector<vector<char>> a;

void solve() {
    memset(dp, -1, sizeof dp);
    cin >> N >> q;
    cout << N << " " << q << "\n";
    while (q--) {
        string s; cin >> s;
        if (s == "poly") {
            cin >> n >> m;
            vector<vector<char>> a(n, vector<char>(m));
            for (int i = n - 1; i >= 0; --i) for (int j = 0; j < m; ++j) cin >> a[i][j];
            // cout << poly_to_string(a) << endl;
            xor_1_bracket(poly_to_string(a), 0);
        }
        else if (s == "perm") {
            vector<int> a(N);
            for (int &val : a) cin >> val;
            xor_1_bracket(perm_to_string(a), 1);
        }
        else {
            vector<array<int, 3>> a(N);
            for (auto &[x, y, z] : a) cin >> x >> y >> z;
            xor_1_bracket(triang_to_string(a), 2);
        }
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}