#include "mars.h"

#include <bits/stdc++.h>
#define lxl unsigned __int128
using namespace std;
using vi = vector<int>;
using mi = map<int, int>;

string tostr(lxl k, int len) {
    string res;

    for (lxl i = 1; i <= k; i <<= 1)
        res += (((k / i) & 1) + '0');

    assert(((int)res.size()) <= len);

    while (((int)res.size()) < len)
        res += '0';

    return res;
}
lxl toint(string s) {
    reverse(s.begin(), s.end());
    lxl res = 0;

    for (auto x : s)
        res = res << 1 | (x - '0');

    return res;
}

const int N = 80;
const int MAXANS = 862;
lxl dp[2][2][2][N];
// you can't push ( or after any bracket
// you can't push ) or X after right bracket

// you neednt push O
// last one isnt )

lxl rs[2][2][N][N];
void initdp() {
    memset(rs, 0, sizeof(rs));
    rs[0][0][0][0] = 1;
    rs[0][1][0][0] = 1;
    rs[1][0][0][0] = 1;
    rs[1][1][0][0] = 1;

    for (int st = 0; st < N; st++)
        for (int limit1 = 0; limit1 < 2; limit1++)
            for (int limit2 = 0; limit2 < 2; limit2++) {
                // start with st left bracket; if the last one is bracket or not
                // start with st left bracket; if the last one is right bracket or not
                memset(dp, 0, sizeof(dp));
                dp[limit2][limit1][0][st] = 1;
                lxl nw;
                int t = 0;

                for (int i = 0; i < N - 1; i++) {
                    t ^= 1;

                    for (int j = 0; j < N / 2; j++) {
                        for (int k = 0; k < 2; k++)
                            for (int l = 0; l < 2; l++) {
                                if (nw = dp[l][k][!t][j]) {
                                    dp[1][1][t][j] += nw;

                                    if (k && j + 1 < N)
                                        dp[1][0][t][j + 1] += nw; //left

                                    if (l && j)
                                        dp[0][0][t][j - 1] += nw; //right

                                    if (k && j)
                                        dp[0][0][t][j] += nw; //X

                                    dp[l][k][!t][j] = 0;
                                }
                            }
                    }

                    for (int k = 0; k < 2; k++)
                        for (int l = 0; l < 2; l++)
                            rs[limit1][limit2][st][i + 1] += dp[k][l][t][0];
                }
            }

    //  cout<<tostr(rs[1][1][0][77]*861,100);
    //  exit(0);
}//

const int maxL = 77;
int tr1[] = {1, 0, 0, 0}, tr2[] = {1, 1, 0, 0}, tr3[] = {0, 1, 0, -1};
lxl incseq(vi a) {

    static int X = 0;
    ++X;

    if (X == 19)
        X = 21;

    lxl res = 0;
    int limit1 = 1, limit2 = 1;
    int l = a.size();
    int st = 0;

    for (int i = 0; i < l; i++) {
        if (i == 75)
            i = 75;

        int x = a[i];

        for (int j = 0; j < x; j++) {
            if ((j == 1 || j == 2) && !limit1)
                continue;

            if (j == 3 && !limit2)
                continue;

            if (j == 3 && st == 0)
                continue;

            res += rs[tr1[j]][tr2[j]][st + tr3[j]][maxL - i - 1];
        }

        st += tr3[x];
        limit1 = tr1[x], limit2 = tr2[x];
    }

    return res;
}


vi decseq(lxl k) {
    static int X = 0;
    ++X;

    if (X == 19)
        X = 21;

    vi res;
    int limit1 = 1, limit2 = 1;
    int st = 0;
    lxl sm = 0;

    for (int i = 0; k; i++) {
        if (i == 72)
            i = 72;

        int x;

        for (int j = 0; j < 4; j++) {
            if ((j == 1 || j == 2) && !limit1)
                continue;

            if (j == 3 && !limit2)
                continue;

            if (j == 3 && st == 0)
                continue;

            lxl nw = rs[tr1[j]][tr2[j]][st + tr3[j]][maxL - i - 1];

            if (nw > k) {
                x = j;
                break;
            } else
                k -= nw, sm += nw;
        }

        res.push_back(x);
        st += tr3[x];
        limit1 = tr1[x], limit2 = tr2[x];
    }

    return res;
}

string inc(vi a, int k) {
    vi seq;
    mi last, cnt;
    int l = a.size();

    for (int i = 0; i < l; i++) {
        int x = a[i];

        if (!x) {
            seq.push_back(0);
            continue;
        }

        if (!cnt[x])
            seq.push_back(1);
        else
            seq.push_back(2);

        cnt[x]++;
        last[x] = i;
    }

    for (auto x : last) {
        int t = cnt[x.first];

        if (t == 1)
            seq[x.second] = 0;
        else
            seq[x.second] = 3;
    }

    for (int i = 0; i < l; i++)
        if (seq[i] == 1)
            for (int j = i + 1; j < l; j++)
                if (seq[j] == 2)
                    seq[j] = 0;
                else
                    break;

    for (int i = 0; i < l; i++)
        if (seq[i] == 3)
            for (int j = i - 1; j >= 0; j--)
                if (seq[j] == 2)
                    seq[j] = 0;
                else
                    break;

    for (int i = 0; i < l; i++)
        if (seq[i] == 2)
            for (int j = i + 1; j < l; j++)
                if (seq[j] == 2)
                    seq[j] = 0;
                else
                    break;

    //for(auto x:seq)
    //  cout<<x<<' ';cout<<endl;

    lxl ns = incseq(seq);
    return tostr(ns * MAXANS + k, 100);
}


vi dec(vi a) {
    vi res;
    stack<int> s;
    int cnt = 0;

    for (auto x : a) {
        if (x == 0) {
            res.push_back(0);
            continue;
        }

        if (x == 1)
            s.push(++cnt);

        res.push_back(s.top());

        if (x == 3)
            s.pop();
    }

    if (s.size())
        res[res.size() - 1] = s.top();

    return res;
}

pair<vi, int> dec(string s, int len) {
    //  cout<<s<<endl;
    lxl all = toint(s);
    lxl sta = all / MAXANS, cnt = all % MAXANS;
    auto seq = decseq(sta);
    seq.resize(len);

    //for(auto x:seq)
    //  cout<<x<<' ';cout<<endl;

    auto x = dec(seq);
    x.resize(len);
    return {x, cnt};
}

vi getreal(vi a, string b) {
    int l = a.size();
    int mx = 0;

    for (int i = 0; i < l; i++)
        if (a[i]) {
            int L = i - 1, R = i + 1;

            while (L >= 0 && b[L] == '1')
                a[L] = a[i], L--;

            while (R < l && b[R] == '1')
                a[R] = a[i], R++;

            mx = max(mx, a[i]);
        }

    for (int i = 0; i < l; i++)
        if (a[i] == 0 && b[i] == '1')
            a[i] = ++mx;

    return a;
}

vi smallest(vi k) {
    int cnt = 0;
    mi id;
    vi res;

    for (auto x : k) {
        if (x == 0)
            res.push_back(0);
        else {
            if (!id[x])
                id[x] = ++cnt;

            res.push_back(id[x]);
        }
    }

    return res;
}


struct dsu {
    vector<int> fa;
    dsu(int k) {
        fa.resize(k + 1);

        for (int i = 1; i <= k; i++)
            fa[i] = i;
    }
    int gf(int k) {
        return k == fa[k] ? k : fa[k] = gf(fa[k]);
    }
    void mrg(int x, int y) {
        int fx = gf(x), fy = gf(y);
        fa[fx] = fy;
    }
};

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

const int HLF = 50;

string process(vector<vector<string>> a, int i, int j, int k, int n) {


    int nowL = n * 2 - 2 - 2 * k;

    if (i >= nowL && j < nowL) { //在左下角
        string res = a[2][0];
        res[k * 2 + 1] = a[1][0][0];
        res[k * 2 + 2] = a[0][0][0];

        for (int i = HLF; i <= HLF + k * 2; i++)
            res[i] = a[2][2][i - HLF];

        res[HLF + k * 2 + 1] = a[1][2][0];
        res[HLF + k * 2 + 2] = a[0][2][0];
        return res;
    }

    if (i < nowL && j >= nowL) { //在右上角
        string res = a[0][2];
        res[k * 2 + 1] = a[0][1][0];
        res[k * 2 + 2] = a[0][0][0];

        for (int i = HLF; i <= HLF + k * 2; i++)
            res[i] = a[2][2][i - HLF];

        res[HLF + k * 2 + 1] = a[2][1][0];
        res[HLF + k * 2 + 2] = a[2][0][0];
        return res;
    }

    if (i < nowL && j < nowL)
        return a[0][0];

    initdp();

    if (k == 0) {

        dsu d(9);

        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                if (a[i][j][0] == '0')
                    continue;

                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];

                    if (x < 0 || x >= 3)
                        continue;

                    if (y < 0 || y >= 3)
                        continue;

                    if (a[x][y][0] == '0')
                        continue;

                    d.mrg(i * 3 + j, x * 3 + y);
                }
            }

        vi state;
        mi visit;

        for (int i = 2; i >= 0; i--) {
            if (a[0][i][0] == '0')
                state.push_back(0);
            else {
                int nw = d.gf(i) + 1;
                visit[nw] = 1;
                state.push_back(nw);
            }
        }

        for (int i = 1; i < 3; i++) {
            if (a[i][0][0] == '0')
                state.push_back(0);
            else {
                int nw = d.gf(i * 3) + 1;
                visit[nw] = 1;
                state.push_back(nw);
            }
        }

        int rs = 0;

        for (int i = 1; i < 3; i++)
            for (int j = 1; j < 3; j++) {
                if (a[i][j][0] == '0')
                    continue;

                rs += !visit[d.gf(i * 3 + j) + 1];
                visit[d.gf(i * 3 + j) + 1] = 1;
            }

        state = smallest(state);

        //for(auto x:state)
        //  cout<<x<<' ';cout<<endl;

        if (k == n - 1)
            return tostr(visit.size(), 100);

        //cout<<inc(state,rs)<<endl;

        return inc(state, rs);
    }

    if (k > 0) {

        dsu d(15 * k + 50);
        int l = k * 2 + 1;

        //cout<<a[2][2]<<endl;

        auto A = dec(a[2][2], l * 2 - 1);

        string pre = a[0][2].substr(HLF, l);
        string suf = a[2][0].substr(HLF, l - 1);
        reverse(suf.begin(), suf.end());

        //cout<<pre+suf<<endl;

        auto state = A.first;

        state = getreal(state, pre + suf);
        state = smallest(state);

        //cout<<endl;
        //for(auto x:state)
        //  cout<<x<<' ';cout<<endl;


        auto ncnt = A.second;
        int sa = 1, sb = sa + l * 2, sc = sb + l * 2, sd = l * 2;
        sb += sa, sc += sb, sd += sc;
        string A1 = a[1][2], A2 = a[0][2];
        string B1 = a[2][1], B2 = a[2][0];
        reverse(B1.begin(), B1.begin() + l);
        reverse(B2.begin(), B2.begin() + l);

        for (int i = 0; i < l; i++) {
            if (state[i] == 0)
                continue;

            if (A1[i] == '0')
                continue;

            d.mrg(sa + state[i], sb + i);
        }

        for (int i = 0; i < l; i++) {
            if (state[l - 1 + i] == 0)
                continue;

            if (B1[i] == '0')
                continue;

            d.mrg(sa + state[l - 1 + i], sb + l + i);
        }

        for (int i = 0; i < l; i++) {
            if (A1[i] == '0')
                continue;

            if (A2[i] == '0')
                continue;

            d.mrg(sb + i, sc + i);
        }

        for (int i = 0; i < l; i++) {
            if (B1[i] == '0')
                continue;

            if (B2[i] == '0')
                continue;

            d.mrg(sb + i + l, sc + i + l);
        }

        for (int i = 0; i < l - 1; i++) {
            if (A1[i] == '0')
                continue;

            if (A1[i + 1] == '0')
                continue;

            d.mrg(sb + i, sb + i + 1);
        }

        for (int i = 0; i < l - 1; i++) {
            if (B1[i] == '0')
                continue;

            if (B1[i + 1] == '0')
                continue;

            d.mrg(sb + i + l, sb + i + l + 1);
        }

        for (int i = 0; i < l - 1; i++) {
            if (A2[i] == '0')
                continue;

            if (A2[i + 1] == '0')
                continue;

            d.mrg(sc + i, sc + i + 1);
        }

        for (int i = 0; i < l - 1; i++) {
            if (B2[i] == '0')
                continue;

            if (B2[i + 1] == '0')
                continue;

            d.mrg(sc + i + l, sc + i + l + 1);
        }

        //      cout<<A2<<endl;
        //      cout<<A1<<endl;
        //      cout<<B2<<endl;
        //      cout<<B1<<endl;

        reverse(A1.begin(), A1.begin() + l);
        reverse(A2.begin(), A2.begin() + l);

        if (a[0][0][0] == '1' && a[0][1][0] == '1')
            d.mrg(sd + 0, sd + 1);

        if (a[0][0][0] == '1' && a[1][0][0] == '1')
            d.mrg(sd + 0, sd + 2);

        if (a[1][0][0] == '1' && a[1][1][0] == '1')
            d.mrg(sd + 2, sd + 3);

        if (a[0][1][0] == '1' && a[1][1][0] == '1')
            d.mrg(sd + 1, sd + 3);

        if (a[0][1][0] == '1' && A2[0] == '1')
            d.mrg(sd + 1, sc + l - 1);

        if (a[1][1][0] == '1' && A1[0] == '1')
            d.mrg(sd + 3, sb + l - 1);

        if (a[1][0][0] == '1' && B2[0] == '1')
            d.mrg(sd + 2, sc + l);

        if (a[1][1][0] == '1' && B1[0] == '1')
            d.mrg(sd + 3, sb + l);

        reverse(A1.begin(), A1.begin() + l);
        reverse(A2.begin(), A2.begin() + l);

        vi S;
        mi visit;

        for (int i = 0; i < l; i++) {
            if (A2[i] == '0')
                S.push_back(0);
            else
                S.push_back(d.gf(sc + i)), visit[d.gf(sc + i)] = 1;
        }

        if (a[0][1][0] == '0')
            S.push_back(0);
        else
            S.push_back(d.gf(sd + 1)), visit[d.gf(sd + 1)] = 1;

        if (a[0][0][0] == '0')
            S.push_back(0);
        else
            S.push_back(d.gf(sd + 0)), visit[d.gf(sd + 0)] = 1;

        if (a[1][0][0] == '0')
            S.push_back(0);
        else
            S.push_back(d.gf(sd + 2)), visit[d.gf(sd + 2)] = 1;

        for (int i = 0; i < l; i++) {
            if (B2[i] == '0')
                S.push_back(0);
            else
                S.push_back(d.gf(sc + i + l)), visit[d.gf(sc + i + l)] = 1;
        }

        int rs = 0;

        for (auto x : state) {
            if (x == 0)
                continue;

            rs += !visit[d.gf(sa + x)];
            visit[d.gf(sa + x)] = 1;
        }

        for (int i = 0; i < l; i++) {
            if (A1[i] == '0')
                continue;

            rs += !visit[d.gf(sb + i)];
            visit[d.gf(sb + i)] = 1;
        }

        if (a[1][1][0] == '1') {
            rs += !visit[d.gf(sd + 3)];
            visit[d.gf(sd + 3)] = 1;
        }

        for (int i = 0; i < l; i++) {
            if (B1[i] == '0')
                continue;

            rs += !visit[d.gf(sb + i + l)];
            visit[d.gf(sb + i + l)] = 1;
        }

        if (k == n - 1)
            return tostr(visit.size() + ncnt, 100);

        S = smallest(S);

        //cout<<endl;for(auto x:S)cout<<x<<' ';

        //  cout<<ncnt+rs<<endl;
        return inc(S, ncnt + rs);
    }


}


void test() {
    initdp();
    vi a = {0, 1, 0, 1, 1, 0, 2, 0, 3, 3, 0, 0, 0, 1, 1, 1, 1};
    string state;

    for (auto x : a)
        state.push_back((!!x) + '0');

    string nw = inc(a, 10);
    //cout<<nw<<endl;
    auto X = dec(nw, 17);
    auto x = X.first;
    auto y = X.second;
    x = getreal(x, state);

    for (auto i : x)
        cout << i << ' ';

    cout << endl;
    exit(0);
}