Maraton Contest1

#include <iostream>
#include <string.h>
#include <math.h>
#include "td/utils/lz4.h"
#include "td/utils/base64.h"
#include "vm/boc.h"
#include "vm/cells/CellSlice.h"
using namespace std;

using PI = pair<int, int>;
using VP = vector<PI>;
using VS = vector<short>;
using VI = vector<int>;
using VC = vector<char>;
using VB = vector<bool>;
using BS = td::BufferSlice;
using CD = td::Ref<vm::Cell>;
using HS = vm::Cell::Hash;
using CB = vm::CellBuilder;
using CS = vm::CellSlice;
#define FOR(i,a,b) for (int i = a; i < b; i ++)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define endl '\n'
#define pb emplace_back
int __lg(int n) {
    int x = 0;
    while ((1 << x) <= n) x++;
    return x - 1;
}
struct WT {
    int n, pw;
    int inf = INT_MAX;
    VI v;
    void init(VI& _init) {
        n = _init.size();
        if (!n) return;
        pw = 2 << __lg(n);
        v.assign(pw << 1, inf);
        for (int i = 0; i < n; i++) v[i + pw] = _init[i];
        for (int i = pw - 1; i > 0; i--) v[i] = min(v[i << 1], v[i << 1 | 1]);
    }
    int get(int l, int r) {
        l += pw, r += pw;
        int rlt = inf;
        while (l < r) {
            if (l & 1) rlt = min(rlt, v[l]);
            if (r & 1) rlt = min(rlt, v[r - 1]);
            l = (l + 1) / 2, r /= 2;
        }
        return rlt;
    }
} wnt;
struct SuffixArray {
    VI v, A, B, cnt, sa, startPoss, lcp;
    int len;
    void rsort(VI& x, VI& y, int offset, int mx, int n) {
        for (int i = 0; i < mx && i < cnt.size(); i++) cnt[i] = 0;
        while (cnt.size() < mx) cnt.pb(0);
        for (int i = 0; i < n; i++) cnt[v[x[i] + offset]] ++;
        for (int i = 1; i < mx; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) y[--cnt[v[x[i] + offset]]] = x[i];
    }
    bool comp(int x, int y) {
        return v[x] == v[y] && v[x + 1] == v[y + 1] && v[x + 2] == v[y + 2];
    }
    void buildSA(int st, int mx) {
        int n = v.size() - st;
        int c0 = n / 3 + (n % 3 > 0), c1 = n / 3 + (n % 3 > 1), c2 = n / 3, cx = c1 + c2;
        v.pb(0), v.pb(0), mx++;
        A.clear();
        for (int i = 0; i < n; i++) if (i % 3) A.pb(i);
        if (B.size() < A.size()) B.resize(A.size());
        rsort(A, B, st + 2, mx, cx);
        rsort(B, A, st + 1, mx, cx);
        rsort(A, B, st, mx, cx);
        int cc = v.size(), cy = v.size() + c1, nx = v.size();
        v.resize(v.size() + cx);
        int cu = 1;
        for (int i = 0; i < cx; i++) {
            if (i && !comp(B[i] + st, B[i - 1] + st)) cu++;
            if (B[i] % 3 == 1) v[cc + B[i] / 3] = cu;
            else v[cy + B[i] / 3] = cu;
        }
        if (sa.size() < v.size()) sa.resize(v.size());
        if (cu == cx) for (int i = 0; i < cx; i++) sa[v[i + nx] - 1 + nx] = i;
        else buildSA(nx, cu);
        A.clear();
        if (n % 3 == 1) A.pb(n - 1);
        for (int i = 0; i < cx; i++) if (sa[i + nx] < c1) A.pb(sa[i + nx] * 3);
        startPoss.clear(), startPoss.resize(n + 1, 0);
        startPoss[n] = -1;
        for (int i = 0; i < cx; i++) {
            if (sa[i + nx] < c1) sa[i + nx] = sa[i + nx] * 3 + 1;
            else sa[i + nx] = (sa[i + nx] - c1) * 3 + 2;
            startPoss[sa[i + nx]] = i;
        }
        rsort(A, B, st, mx, c0);
        function<bool(int, int)> cmp = [&](int x, int y) -> bool {
            if (v[x + st] != v[y + st]) return v[x + st] < v[y + st];
            if (x % 3 == 2) return cmp(x + 1, y + 1);
            return startPoss[x + 1] < startPoss[y + 1];
        };
        cu = st;
        for (int i = 0, j = 0; i < cx || j < c0;) {
            if (i == cx) sa[cu++] = B[j++];
            else if (j == c0) sa[cu++] = sa[i + nx], i++;
            else if (cmp(sa[i + nx], B[j])) sa[cu++] = sa[i + nx], i++;
            else sa[cu++] = B[j++];
        }
    }
    void LCPcalc() {
        startPoss.resize(len + 1), lcp.resize(len + 1);
        for (int i = 0; i <= len; i++) startPoss[sa[i]] = i;
        int tp = 0;
        for (int i = 0; i < len; i++) {
            if (tp) tp--;
            while (v[sa[startPoss[i] - 1] + tp] == v[i + tp]) tp++;
            lcp[startPoss[i]] = tp;
        }
    }
    void init(VC& _init) {
        len = _init.size();
        v.clear();
        for (auto u : _init) v.pb(static_cast<int>(u));
        int mx = 0;
        for (int i = 0; i < v.size(); i++) {
            v[i] ++;
            if (v[i] > mx) mx = v[i];
        }
        v.pb(0);
        buildSA(0, mx + 1);
        A.clear(), B.clear(), cnt.clear();
        sa.resize(len + 1);
        LCPcalc();
        wnt.init(lcp);
        v.clear();
    };
    int getLCP(int x, int y) {
        if (x == y) return len - x;
        x = startPoss[x] + 1, y = startPoss[y] + 1;
        if (x > y) swap(x, y);
        return wnt.get(x, y);
    }
    VI Gsa() { auto it = sa; sa.clear(); return it; }
    VI Gla() { auto it = lcp; lcp.clear(); return it; }
} sa;
struct Node {
    bool sp = false;
    VI chd;
    VB data;
    Node() {
        sp = false;
        chd.clear();
        data.clear();
    }
};
vector<Node> nds;
int get(int u, int startPoss) { return u >> (7 - startPoss) & 1; }
void output(VB& outdata, int val, int len) { FOR(i,0,len) outdata.pb(val >> (len - 1 - i) & 1); }
void output(VB& outdata, bool val) { output(outdata, val, 1); }
VB bufVec, his;
bool inputOneBit() { bool ret = bufVec.back(); bufVec.pop_back(); his.pb(ret); return ret; }
int input(int len = 1) { int ret = 0; FOR(i,0,len) ret = ret << 1 | inputOneBit(); return ret; }
void insertBuf(VB tp) { reverse(all(tp)); for (auto v : tp) bufVec.pb(v); }
BS buffData;
unsigned char tmpchar[1 << 22];
struct state {
    int curVal;
    char curOperator;
    int startPos;
    int lastPos;
    state(int cv = 1e9, char cu = 0, int sp = 0, int lp = 0) : curVal(cv), curOperator(cu), startPos(sp), lastPos(lp) {}
    bool operator<(const state& A) {
        return curVal < A.curVal;
    }
};
struct bit {
    vector<state> v;
    int n;
    void init(int m) {
        n = m + 1;
        v.resize(n);
    }
    state get(int k) {
        k = n - k;
        state ret = state();
        while (k) {
            if (v[k] < ret) ret = v[k];
            k -= k & -k;
        }
        return ret;
    };
    void upd(int k, state x) {
        k = n - k;
        while (k <= n) {
            if (x < v[k]) v[k] = x;
            k += k & -k;
        }
    };
}bt[2];
map<HS, int> mp;
int dfs(CD rt) {
    if (mp.count(rt.get()->get_hash())) return mp[rt.get()->get_hash()];
    int cz = nds.size();
    mp[rt.get()->get_hash()] = cz;
    nds.pb(Node());
    CS cs = vm::load_cell_slice_special(rt, nds[cz].sp);
    for (int i = 0; i < sz(cs); i++) nds[cz].data.pb(cs.data_bits()[i]);
    CB cb;
    cb.append_cellslice(cs);
    for (int i = 0; i < cb.get_refs_cnt(); i++) {
        int tp = dfs(cb.get_ref(i));
        nds[cz].chd.pb(tp);
    }
    return cz;
}
const int MAXN = 1024;
const int hCNT = 2;
int constant[hCNT][MAXN] = { {1141,1118,1706,504,91,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1520,891,325,262,123,124,87,93,47,69,39,53,36,44,30,36,19,29,17,19,25,26,15,11,16,18,7,17,8,9,7,12,9,6,8,10,8,5,4,5,4,6,7,4,1,7,2,5,3,8,6,4,4,6,2,1,5,3,5,2,1,2,5,378,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, };
VB coding[hCNT][MAXN * 3];
vector<vector<VI>> chd(hCNT, vector<VI>(MAXN, VI()));
void huffmanBuild() {
    for (int pp = 0; pp < hCNT; pp++) {
        set<pair<int, int>> st;
        for (int i = 0; i < MAXN; i++) st.insert({ constant[pp][i], i });
        while (st.size() > 1) {
            auto x = *st.begin();
            st.erase(st.begin());
            auto y = *st.begin();
            st.erase(st.begin());
            chd[pp].push_back(VI(0));
            chd[pp].back().push_back(abs(x.second)), chd[pp].back().push_back(abs(y.second));
            st.emplace(x.first + y.first, chd[pp].size() - 1);
        }
        for (int i = 0; i < chd[pp].size(); i++) coding[pp][i].clear();
        for (int i = chd[pp].size() - 1; i >= MAXN; i--) {
            for (int j = 0; j < chd[pp][i].size(); j++) {
                int u = chd[pp][i][j];
                coding[pp][u] = coding[pp][i];
                coding[pp][u].push_back(j);
            }
        }
    }
}
int hufR(int tx) {
    int p = MAXN * 2 - 2;
    while (p >= MAXN) p = chd[tx][p][input()];
    return p;
}
void hufW(VB& ret, int tx, int val) {
    for (auto u : coding[tx][val]) output(ret, u);
}

BS compress(BS& data) {
    buffData = data.copy();
    CD root = vm::std_boc_deserialize(buffData).move_as_ok();
    nds.clear();
    dfs(root);
    int N = nds.size();
    auto xx = nds;
    VI id(N), _id(N);
    FOR(i, 0, N) id[i] = i;
    int exN = 0;
    for (int i = 0; i < N; i++) exN += nds[i].sp;
    sort(all(id), [&](int x, int y) {
        if (nds[x].sp != nds[y].sp) return nds[x].sp > nds[y].sp;
        if (nds[x].data.size() != nds[y].data.size()) return nds[x].data.size() < nds[y].data.size();
        for (int j = 0; j < min(nds[x].data.size(), nds[y].data.size()); j++) {
            if (nds[x].data[j] > nds[y].data[j]) return true;
            if (nds[x].data[j] < nds[y].data[j]) return false;
        }
        return x < y;
        });
    FOR(i, 0, N) _id[id[i]] = i;
    VB ret(0);
    int l = 0;
    while ((1 << l) < N) l++;
    output(ret, l, 8);
    output(ret, N, l);
    output(ret, exN, l);
    output(ret, _id[0], l);
    FOR(i, 0, N) nds[i] = xx[id[i]];
    xx.clear();
    FOR(i, 0, N) for (auto& x : nds[i].chd) x = _id[x];
    VP tt;
    VI an(100);
    FOR(i, 0, exN) {
        int t = 0;
        for (int j = 0; j < 8; j++) t = t << 1 | nds[i].data[j];
        an[t] ++;
    }
    FOR(i, 1, 5) output(ret, an[i], l);
    VP gas, gg;
    for (int i = exN; i < N; i++) {
        int x = nds[i].chd.size();
        if (!gas.empty() && gas.back().first == x && gas.back().second + 1 < 1024) gas.back().second++;
        else gas.emplace_back(x, 1);
    }
    for (auto [u, v] : gas) hufW(ret, 0, u), hufW(ret, 1, v);
    cerr << ret.size() << endl;
    VP tmp;
    for (int i = exN; i < N; i++) {
        int x = nds[i].data.size();
        if (!tmp.empty() && tmp.back().first == x) tmp.back().second++;
        else tmp.pb(x, 1);
    }
    for (auto [x, y] : tmp) {
        output(ret, x, 10);
        output(ret, y, 13);
    }
    cerr << ret.size() << endl;
    FOR(i, 0, N) for (auto u : nds[i].chd) output(ret, u, l);
    cerr << ret.size() << endl;

    FOR(i, 0, exN) {
        int lcp = 0;
        while (i && lcp < nds[i].data.size() && lcp < nds[i - 1].data.size() && lcp + 1 < 16 && nds[i].data[lcp] == nds[i - 1].data[lcp]) lcp++;
        output(ret, lcp, 4);
        for (int j = lcp; j < nds[i].data.size(); j++) output(ret, nds[i].data[j]);
    }
    cerr << ret.size() << endl;
    VC tempVec;
    for (int i = exN; i < N; i++) for (auto u : nds[i].data) tempVec.pb(u);
    sa.init(tempVec);
    auto lcp = sa.Gla();
    auto sa_id = sa.Gsa();
    int n = tempVec.size();
    vector<state> dp(n + 1);
    dp[0].curVal = 0;
    VI _sa_id(n);
    for (int i = 1; i <= n; i++) _sa_id[sa_id[i]] = i;
    auto write = [&](int u, int len) {
        for (int i = 0; i < len; i++) ret.pb(u >> (len - 1 - i) & 1);
    };
    VS firstID(n), secondID(n);
    int curID = exN, sum = 0;
    for (int i = 0; i < n; i++) {
        while (curID < N && sum + nds[curID].data.size() <= i) sum += nds[curID++].data.size();
        firstID[i] = curID;
        secondID[i] = i - sum;
    }
    int m = __lg(n);
    int inf = 1e9;
    bt[0].init(n + 1); bt[1].init(n + 1);
    for (int i = 0; i <= n; i++) {
        if (i) {
            dp[i] = bt[1].get(i);
            auto xx = bt[0].get(i);
            xx.curVal += i;
            if (xx < dp[i]) dp[i] = xx;
        }
        if (i == n) break;
        state cst = { dp[i].curVal + 8 - i , 0, i, i };
        bt[0].upd(min(n, i + 128), cst);
        int val = 0, startPoss = 0;
        int mn = inf;
        for (int j = _sa_id[i] - 1; j >= max(1, _sa_id[i] - 30); j--) {
            mn = min(mn, lcp[j + 1]);
            if (sa_id[j] < i) {
                val = mn;
                startPoss = i - sa_id[j];
                break;
            }
        }
        mn = inf;
        for (int j = _sa_id[i] + 1; j <= min(_sa_id[i] + 30, n); j++) {
            mn = min(mn, lcp[j]);
            if (sa_id[j] < i && mn > val) {
                val = mn;
                startPoss = i - sa_id[j];
                break;
            }
        }
        val = min(val, 1 << 9);
        int cans = 12 + m;
        char tp = 2;
        cst = { dp[i].curVal + cans, tp, startPoss, i };
        bt[1].upd(i + val, cst);
        int id = firstID[i];
        int p = i;
        if (!secondID[i] || i % 3 == 1) for (int ii = 0; ii < 3; ii++) {
            if (id - ii - 1 < exN || nds[id - ii - 1].data.size() == 0) break;
            p -= nds[id - ii - 1].data.size();
            int len = min(128, sa.getLCP(i, p));
            int cans = 7;
            char tp;
            if (!ii) cans += 2, tp = 1;
            else {
                cans += (ii + 3); tp = ii + 2;
                if (ii == 2) cans--;
            }
            cst = { dp[i].curVal + cans, tp, 0, i };
            bt[1].upd(i + len, cst);
        }
    }
    vector<tuple<int, int, int>> ttt;
    int p = n, mx = 0;
    while (p) {
        ttt.pb(dp[p].curOperator, p - dp[p].lastPos, dp[p].startPos);
        if (dp[p].curOperator == 2) mx = max(mx, dp[p].startPos);
        p = dp[p].lastPos;
    }
    reverse(all(ttt));
    int MM = 0;
    while ((1 << MM) <= mx) MM++;
    write(MM, 5);
    for (auto [x, y, z] : ttt) {
        for (int p = 0; p < 5; p++) {
            if (p == x) {
                if (p != 4) write(1, 1);
                if (!p) {
                    write(y - 1, 7);
                    for (int i = z; i < z + y; i++) ret.pb(tempVec[i]);
                }
                else if (p == 2) write(y - 1, 9), write(z, MM);
                else write(y - 1, 7);
                break;
            }
            else write(0, 1);
        }
    }
    while (ret.size() % 8) ret.pb(0);
    for (int i = 0; i < ret.size(); i += 8) {
        tmpchar[i] = 0;
        for (int j = 0; j < 8; j++) tmpchar[i / 8] = tmpchar[i / 8] << 1 | ret[i + j];
    }
    cerr << ret.size() << endl;
    buffData = BS(td::Slice(tmpchar, ret.size() / 8));
    return td::lz4_compress(buffData);
}

BS decompress(BS& data) {
    cerr << "here\n";
    buffData = td::lz4_decompress(data, 2 << 20).move_as_ok();
    VB tempVec(0);
    FOR(i,0,buffData.length()) FOR(j,0,8) tempVec.pb(get(buffData[i], j));
    insertBuf(tempVec);
    int l = input(8);
    int N = input(l);
    nds.clear(), nds.resize(N);
    int exN = input(l);
    int root = input(l);
    VI an(100);
    FOR(i,1,5) an[i] = input(l);
    VI len(N), chdsz(N);
    for (int i = 0; i < exN; i++) {
        if (i < an[2]) len[i] = 264, chdsz[i] = 0;
        else if (i < an[2] + an[3]) len[i] = 280, chdsz[i] = 1;
        else if (i < an[1] + an[2] + an[3]) len[i] = 288, chdsz[i] = 0;
        else len[i] = 552, chdsz[i] = 2;
    }

    int curstartPosinter = exN;
    while (curstartPosinter < N) {
        int x = hufR(0);
        int y = hufR(1);
        while (y--) chdsz[curstartPosinter++] = x;
    }
    curstartPosinter = exN;
    while (curstartPosinter < N) {
        int x = input(10);
        int lx = input(13);
        while (lx--) len[curstartPosinter++] = x;
    }
    for (int i = 0; i < exN; i++) nds[i].sp = true;
    for (int i = 0; i < N; i++) for (int j = 0; j < chdsz[i]; j++) nds[i].chd.pb(input(l));

    VI lastPP(N);
    for (int i = 0; i < exN; i++) {
        int lcp = input(4);
        VB tmp;
        for (int j = 0; j < lcp; j++) tmp.pb(his[lastPP[i - 1] + j]);
        insertBuf(tmp);
        lastPP[i] = his.size();
        while (nds[i].data.size() < len[i]) nds[i].data.pb(input());
    }
    int MM = input(5);
    int curID = exN, sum = 0, tempSum = 0;
    for (int i = exN; i < N; i++) tempSum += len[i];
    VI firstID(tempSum);
    for (int i = 0; i < tempSum; i++) {
        while (curID < N && sum + len[curID] <= i) sum += len[curID++];
        firstID[i] = curID;
    }
    tempVec.clear();
    while (tempVec.size() < tempSum) {
        int zcnt = 0;
        while (!input()) if (++zcnt == 4) break;
        if (!zcnt) {
            int len = input(7) + 1;
            for (int i = 0; i < len; i++) tempVec.pb(input());
        }
        else if (zcnt ==2) {
            int len = input(9) + 1;
            int st = input(MM);
            for (int i = 0; i < len; i++) tempVec.pb(tempVec[tempVec.size() - st]);
        }
        else {
            if (zcnt == 1) zcnt--;
            else zcnt -= 2;
            int lx = input(7) + 1;
            int tmpSum = 0;
            for (int i = 0; i <= zcnt; i++) tmpSum += len[firstID[tempVec.size()] - 1 - i];
            for (int i = 0; i < lx; i++) tempVec.pb(tempVec[tempVec.size() - tmpSum]);
        }
    }

    reverse(all(tempVec));
    for (int i = exN; i < N; i++) for (int j = 0; j < len[i]; j++) nds[i].data.pb(tempVec.back()), tempVec.pop_back();
    vector<CD> cells(N);
    VB vis(N, 0);
    auto _dfs = [&](auto self, int i) {
        if (vis[i]) return;
        vis[i] = 1;
        CB cb;
        for (auto u : nds[i].chd) {
            self(self, u);
            cb.store_ref(cells[u]);
        }
        for (auto u : nds[i].data) cb.store_bool_bool(u);
        cells[i] = cb.finalize(nds[i].sp);
    };
    _dfs(_dfs, root);
    buffData = vm::std_boc_serialize(cells[root], 31).move_as_ok();
    return buffData.copy();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string mode;
    cin >> mode;
    CHECK(mode == "compress" || mode == "decompress");

    string base64_data;
    cin >> base64_data;
    CHECK(!base64_data.empty());
    BS data(td::base64_decode(base64_data).move_as_ok());
    huffmanBuild();
    if (mode == "compress") {
        data = compress(data);
    }
    else {
        data = decompress(data);
    }

    cout << td::base64_encode(data) << endl;
    return 0;
}