/* Christoph Durr - 2024
Bracket-and-bar Sequences
https://qoj.ac/contest/1465/problem/4824

There are two main ingredients to the solution

## Simplifying the syntax

F = emptystring or '(' F '|' F ')' F 

## Encoding

We use the binary encoding where '(' corresponds to 1 and '|' or ')' to 0.
The code length is 3n

*/

#include <iostream>
#include <stack>
#include <cassert> 

using namespace std;

typedef unsigned long long ll;
typedef pair<int, ll> pil;

char word[1024] = "((|)|)(|)";
int pos=0;

// T[n] = number of strings of length 3n
ll T[26] = {1, 1};
ll L[25][25][25];           // lower bound of signature interval
ll U[25][25][25] = {1};     // upper bound

void fill() {
    for (int n = 2; n <= 25; n++) {
        for (int a=0; a < n; a++)
            for (int b=0; a + b < n; b++) {
                int c = n - 1 - a - b;
                L[a][b][c] = T[n];
                T[n] += T[a] * T[b] * T[c];
                U[a][b][c] = T[n];
            }
        // cout << "T[" << n << "] = " << T[n] << endl;
        // log(T[25], 2) == 63.8...
    }
}

void signature(int n, ll code, int &a, int &b, int &c) {
    ll total = 0;
    for (a=0; a < n; a++)
        for (b=0; a+b < n; b++) {
            c = n - 1 - a - b;
            if (U[a][b][c] > code)
                return;
        }
    // we should never reach this point
    cout << "code was " << code << " n=" << n << endl;
    assert(false);
}

void decode(int n, ll code) {
    if (n == 0)
        return;
    assert(code < T[n]);
    int a, b, c;
    signature(n, code, a, b, c);
    int ia, ib, ic;
    code -= L[a][b][c];
    ic = code % T[c];
    code /= T[c];
    ib = code % T[b];
    code /= T[b];
    ia = code;
    cout << "(";
    decode(a, ia);
    cout << "|";
    decode(b, ib);
    cout << ")";
    decode(c, ic);
}

void consume(char expectation) {
    assert(word[pos] == expectation);
    pos++;
}

/* encodes the string in `word`.
   assumes that initially pos == 0
*/ 
pil encode() {
    const char head = word[pos];
    if (word[pos] != '(')
        return {0, 0};
    consume('(');
    pil A = encode();
    consume('|');
    pil B = encode();
    consume(')');
    pil C = encode();
    int a = A.first;
    int b = B.first;
    int c = C.first;
    ll ia = A.second;
    ll ib = B.second;
    ll ic = C.second;
    int n = a + b + c + 1;
    ll code = L[a][b][c] + ic + T[c] * (ib + T[b] * ia);
    return {n, code};
}

int main(int argc, char const *argv[])
{
    fill();
    string mode;
    int test_cases, n;
    ll code;
    cin >> mode >> test_cases;
    if (mode == "encode")
        while (test_cases --> 0) {
            cin >> n >> word;   
            pos = 0;
            cout << encode().second << endl;
        }
    else // decode
        while (test_cases --> 0) {
            cin >> n >> code;  
            decode(n, code);
            cout << endl;
        }
    return 0;
}

int _main(int argc, char const *argv[])
{
    fill();
    for (int a=0; a<=2; a++)
        for (int b=0; b<=2; b++)
            for (int c=0; c<=2; c++) 
                cout << a << " " << b << " " << c << " L=" << L[a][b][c] 
                    << " U=" << U[a][b][c] << endl;
    cout << encode().second << endl;
    return 0;
}