#include <bits/stdc++.h>
#include "abc.h"

using namespace std;

int p[3005], fa[3005], a[3005], dy[3005];
vector<int> sf;
bool vis[3005];

int findf(int n) {
    if (fa[n] == n)
        return n;

    return fa[n] = findf(fa[n]);
}
void paixu(int l, int r) {
    if (l == r)
        return;

    register int mid = (l + r) >> 1, yb = (r - l + 1) >> 1, i;
    vector <int> v;

    for (i = l; i <= r; ++i)
        dy[i] = (a[i] < yb) ? (a[i] + yb) : (a[i] - yb);

    for (i = 0; i ^ yb << 1; ++i)
        fa[i] = i;

    for (i = 0; i ^ yb << 1; ++i)
        vis[i] = 0;

    for (i = l; i <= mid; ++i)
		fa[findf(a[i])] = findf(dy[i + yb]), fa[findf(dy[i])] = findf(a[i + yb]);

    for (i = 0; i ^ yb; ++i) {
        if (vis[findf(i + yb)])
            continue;

        vis[findf(i)] = 1;
    }

    for (i = l; i <= mid; ++i)
        if (vis[findf(a[i + yb])])
            sf.push_back(1), swap(a[i], a[i + yb]);
        else
            sf.push_back(0);

    for (i = 0; i ^ yb; ++i)
        v.push_back(0);

    for (i = l; i <= mid; ++i)
        if (a[i] >= yb)
            v[a[i] - yb] = 1, a[i] -= yb;

    for (i = mid + 1; i <= r; ++i)
        if (a[i] >= yb)
            a[i] -= yb;

    paixu(l, mid), paixu(mid + 1, r), sf.insert(sf.end(), v.begin(), v.end());
}

int sz[100005], pos[100005];

inline bool bi(int x, int y) {
    return sz[x] < sz[y];
}

int alice(const int n, const char names[][5], const unsigned short numbers[], bool out[]) {
    register int i, j, len, sth, cnt = 0;
    for (i = 1; i <= n; ++i) {
        len = strlen(names[i - 1]), sth = 1, sz[i] = 0;

        for (j = 1; j ^ len; ++j)
            sz[i] += (sth *= 26);

        sth = 0;

        for (j = 0; j ^ len; ++j)
            sth = sth * 26 + names[i - 1][j] - 'a';

        sz[i] += sth, ++sz[i];
    }

    for (i = 1; i <= n; ++i)
        pos[i] = i;

    sort(pos + 1, pos + n + 1, bi), sf.clear();

    for (i = 1; i <= n; ++i)
        a[i] = pos[i] - 1;

    for (i = n + 1; i ^ 1025; ++i)
        a[i] = i - 1;

    paixu(1, 1024);

    for (i = 1; i <= n; i++) {
        out[cnt] = 0, ++cnt;

        for (j = 18; j ^ -1; --j)
            if (sz[pos[i]] & (1 << j))
                out[cnt] = 1, ++cnt;
            else
                out[cnt] = 0, ++cnt;

        for (j = 0; j ^ 16; ++j)
            if (numbers[pos[i] - 1] & (1 << j))
                out[cnt] = 1, ++cnt;
            else
                out[cnt] = 0, ++cnt;

        for (j = 1; j ^ 4; ++j)
            out[cnt] = 0, ++cnt;
    }

    for (i = 0; i ^ sf.size(); ++i)
        out[cnt] = sf[i], ++cnt;

    return cnt;
}

pair<int, int>bs[100005];
int sr[100005], sc[100005];

inline bool bibi(int x, int y) {
    return bs[x].second < bs[y].second;
}
int bob(const int m, const char senders[][5], const char recipients[][5], bool out[]) {
    for (int i = 1; i <= m; i++) {
        int len = strlen(senders[i - 1]);
        sr[i] = 0;
        int sth = 1;

        for (int j = 1; j <= len - 1; j++) {
            sth *= 26;
            sr[i] += sth;
        }

        sth = 0;

        for (int j = 0; j < len; j++) {
            sth = sth * 26 + senders[i - 1][j] - 'a';
        }

        sr[i] += sth;
        len = strlen(recipients[i - 1]);
        sc[i] = 0;
        sth = 1;

        for (int j = 1; j <= len - 1; j++) {
            sth *= 26;
            sc[i] += sth;
        }

        sth = 0;

        for (int j = 0; j < len; j++) {
            sth = sth * 26 + recipients[i - 1][j] - 'a';
        }

        sc[i] += sth;
        sr[i]++;
        sc[i]++;
        //printf("%d %d\n",sr[i],sc[i]);
    }

    for (int i = 1; i <= m; i++)
        bs[i] = make_pair(sr[i], sc[i]), pos[i] = i;

    sort(bs + 1, bs + m + 1);
    sort(pos + 1, pos + m + 1, bibi);

    for (int i = 1; i <= m; i++) {
        a[pos[i]] = i - 1;
    }

    for (int i = m + 1; i <= 1024; i++)
        a[i] = i - 1;

    sf.clear();
    paixu(1, 1024);
    int cnt = 0;

    for (int i = 1; i <= m; i++) {
        out[cnt] = 1;
        cnt++;

        for (int j = 18; j >= 0; j--) {
            if (bs[i].first & (1 << j))
                out[cnt] = 1, cnt++;
            else
                out[cnt] = 0, cnt++;
        }

        for (int j = 18; j >= 0; j--) {
            if (bs[i].second & (1 << j))
                out[cnt] = 1, cnt++;
            else
                out[cnt] = 0, cnt++;
        }
    }

    for (int i = 0; i < sf.size(); i++) {
        out[cnt] = sf[i];
        cnt++;
    }

    return cnt;
}
int nowa = 0, nowb = 0;

struct xinxi {
    int wz[40];
} tx[4005], tb[4005];
int La, Lb, cz[20000005], czx[20000005], czy[20000005], ttt, zs, bx[100005], by[100005], jg[100005], cnt;
void sort_shuangdiao(int l, int r) {
    if (l == r)
        return;

    int mid = ((l + r) >> 1), yb = ((r - l + 1) >> 1);

    for (int i = l; i <= mid; i++) {
        bx[++cnt] = i;
        by[cnt] = i + yb;
        int now = La + Lb;
        cz[++ttt] = 4;
        czx[ttt] = tx[i].wz[1];
        czy[ttt] = tx[i + yb].wz[1];
        now = ttt;

        for (int j = 20; j >= 2; j--) {
            cz[++ttt] = 4;
            czx[ttt] = tx[i].wz[j];
            czy[ttt] = tx[i + yb].wz[j];
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = now;
            now = ttt;
            cz[++ttt] = 13;
            czx[ttt] = tx[i].wz[j];
            czy[ttt] = tx[i + yb].wz[j];
            cz[++ttt] = 8;
            czx[ttt] = ttt - 1;
            czy[ttt] = now;
            now = ttt;
        }

        cz[++ttt] = 7;
        czx[ttt] = now;
        czy[ttt] = now;
        jg[cnt] = now;
        int fnow = ttt;

        for (int j = 1; j <= 39; j++) {
            cz[++ttt] = 8;
            czx[ttt] = now;
            czy[ttt] = tx[i].wz[j];
            cz[++ttt] = 8;
            czx[ttt] = fnow;
            czy[ttt] = tx[i + yb].wz[j];
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            int sth = ttt;
            cz[++ttt] = 8;
            czx[ttt] = fnow;
            czy[ttt] = tx[i].wz[j];
            cz[++ttt] = 8;
            czx[ttt] = now;
            czy[ttt] = tx[i + yb].wz[j];
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            tx[i].wz[j] = sth;
            tx[i + yb].wz[j] = ttt;
        }
    }

    sort_shuangdiao(l, mid), sort_shuangdiao(mid + 1, r);
}
void findjiaohuana(int l, int r) {
    if (l == r)
        return;

    int mid = ((l + r) >> 1), yb = ((r - l + 1) >> 1);

    for (int i = l; i <= mid; i++) {
        int sth = nowa;
        ++nowa, cz[++ttt] = 7, czx[ttt] = czy[ttt] = sth;
        int fsth = ttt;

        for (int j = 1; j <= 16; j++) {
            int x1 = i, x2 = i + yb;
            cz[++ttt] = 8;
            czx[ttt] = tb[x1].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 8;
            czx[ttt] = tb[x2].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            int gre = ttt;
            cz[++ttt] = 8;
            czx[ttt] = tb[x1].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 8;
            czx[ttt] = tb[x2].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1, czy[ttt] = ttt - 2, tb[x1].wz[j] = gre, tb[x2].wz[j] = ttt;
        }
    }

    findjiaohuana(l, mid), findjiaohuana(mid + 1, r);

    for (int i = l; i <= mid; i++) {
        int sth = nowa;
        nowa++;
        cz[++ttt] = 7;
        czx[ttt] = czy[ttt] = sth;
        int fsth = ttt;

        for (int j = 1; j <= 16; j++) {
            int x1 = i, x2 = i + yb;
            cz[++ttt] = 8;
            czx[ttt] = tb[x1].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 8;
            czx[ttt] = tb[x2].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            int gre = ttt;
            cz[++ttt] = 8;
            czx[ttt] = tb[x1].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 8;
            czx[ttt] = tb[x2].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            tb[x1].wz[j] = gre;
            tb[x2].wz[j] = ttt;
        }
    }
}
void findjiaohuanb(int l, int r) {
    if (l == r)
        return;

    int mid = ((l + r) >> 1), yb = ((r - l + 1) >> 1);

    for (int i = l; i <= mid; i++) {
        int sth = nowb;
        nowb++;
        cz[++ttt] = 7;
        czx[ttt] = czy[ttt] = sth;
        int fsth = ttt;

        for (int j = 1; j <= 36; j++) {
            int x1 = i, x2 = i + yb;
            cz[++ttt] = 8;
            czx[ttt] = tb[x1].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 8;
            czx[ttt] = tb[x2].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            int gre = ttt;
            cz[++ttt] = 8;
            czx[ttt] = tb[x1].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 8;
            czx[ttt] = tb[x2].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            tb[x1].wz[j] = gre;
            tb[x2].wz[j] = ttt;
        }
    }

    findjiaohuanb(l, mid);
    findjiaohuanb(mid + 1, r);

    for (int i = l; i <= mid; i++) {
        int sth = nowb;
        nowb++;
        cz[++ttt] = 7;
        czx[ttt] = czy[ttt] = sth;
        int fsth = ttt;

        for (int j = 1; j <= 36; j++) {
            int x1 = i, x2 = i + yb;
            cz[++ttt] = 8;
            czx[ttt] = tb[x1].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 8;
            czx[ttt] = tb[x2].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            int gre = ttt;
            cz[++ttt] = 8;
            czx[ttt] = tb[x1].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 8;
            czx[ttt] = tb[x2].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            tb[x1].wz[j] = gre;
            tb[x2].wz[j] = ttt;
        }
    }
}
int nz[16];
int scc[100005];
// returns l
int circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int out[][16]) {
    La = la;
    Lb = lb;
    int n = (la - 10240) / 39, m = (lb - 10240) / 39;
    ttt = la + lb - 1;
    cz[++ttt] = 0;
    czx[ttt] = czy[ttt] = 0;
    cz[++ttt] = 15;
    czx[ttt] = czy[ttt] = 0;
    nowa = n * 39;
    nowb = m * 39 + la;
    zs = 0;

    for (int i = n; i >= 1; i--) {
        ++zs;

        for (int j = 1; j <= 39; j++) {
            tx[zs].wz[j] = (i - 1) * 39 + j - 1;
        }
    }

    for (int i = 1; i <= 2048 - n - m; i++) {
        ++zs;

        for (int j = 1; j <= 39; j++) {
            tx[zs].wz[j] = la + lb;
        }
    }

    for (int i = 1; i <= m; i++) {
        ++zs;

        for (int j = 1; j <= 39; j++) {
            tx[zs].wz[j] = (i - 1) * 39 + j - 1 + la;
        }
    }

    cnt = 0;
    sort_shuangdiao(1, 2048);

    for (int i = 1; i <= 2048; i++) {
        for (int j = 0; j <= 15; j++) {
            cz[++ttt] = 8;
            czx[ttt] = nz[j];
            czy[ttt] = tx[i].wz[1];
            nz[j] = ttt;
            cz[++ttt] = 2;
            czx[ttt] = tx[i].wz[j + 21];
            czy[ttt] = tx[i].wz[1];
            cz[++ttt] = 14;
            czx[ttt] = nz[j];
            czy[ttt] = ttt - 1;
            nz[j] = ttt;
        }

        for (int j = 2; j <= 20; j++) {
            cz[++ttt] = 2;
            czx[ttt] = tx[i].wz[j];
            czy[ttt] = tx[i].wz[1];
            tx[i].wz[j] = ttt;
            cz[++ttt] = 8;
            czx[ttt] = tx[i].wz[1];
            czy[ttt] = tx[i].wz[j + 19];
            cz[++ttt] = 14;
            czx[ttt] = tx[i].wz[j];
            czy[ttt] = ttt - 1;
            tx[i].wz[j] = ttt;
        }

        for (int j = 21; j <= 36; j++) {
            tx[i].wz[j] = la + lb;
            cz[++ttt] = 8;
            czx[ttt] = tx[i].wz[1];
            czy[ttt] = nz[j - 21];
            cz[++ttt] = 14;
            czx[ttt] = tx[i].wz[j];
            czy[ttt] = ttt - 1;
            tx[i].wz[j] = ttt;
        }
    }

    for (int i = cnt; i >= 1; i--) {
        int sth = jg[i];
        cz[++ttt] = 7;
        czx[ttt] = czy[ttt] = sth;
        int fsth = ttt;
        int x1 = bx[i], x2 = by[i];

        for (int j = 1; j <= 36; j++) {
            cz[++ttt] = 8;
            czx[ttt] = tx[x1].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 8;
            czx[ttt] = tx[x2].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            int gre = ttt;
            cz[++ttt] = 8;
            czx[ttt] = tx[x1].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 8;
            czx[ttt] = tx[x2].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            tx[x1].wz[j] = gre;
            tx[x2].wz[j] = ttt;
        }
    }

    zs = 0;

    for (int i = 2048 - m + 1; i <= 2048; i++) {
        ++zs;

        for (int j = 1; j <= 39; j++)
            tb[zs].wz[j] = tx[i].wz[j];
    }

    for (int i = 1; i <= 1024 - m; i++) {
        ++zs;

        for (int j = 1; j <= 39; j++)
            tb[zs].wz[j] = la + lb;
    }

    findjiaohuanb(1, 1024);
    zs = 0;

    for (int i = 2048 - m + 1; i <= 2048; i++) {
        zs++;

        for (int j = 1; j <= 39; j++)
            tx[i].wz[j] = tb[zs].wz[j];
    }

    cnt = 0;
    sort_shuangdiao(1, 2048);

    for (int i = 2047; i >= 1; i--) {
        int eq = la + lb + 1;

        for (int j = 0; j <= 18; j++) {
            cz[++ttt] = 9;
            czx[ttt] = tx[i].wz[j + 2];
            czy[ttt] = tx[i + 1].wz[j + 2];
            cz[++ttt] = 8;
            czx[ttt] = eq;
            czy[ttt] = ttt - 1;
            eq = ttt;
        }

        for (int j = 0; j <= 15; j++) {
            cz[++ttt] = 8;
            czx[ttt] = eq;
            czy[ttt] = tx[i + 1].wz[j + 21];
            nz[j] = ttt;
        }

        int jw = la + lb;

        for (int j = 0; j <= 15; j++) {
            cz[++ttt] = 6;
            czx[ttt] = tx[i].wz[j + 21];
            czy[ttt] = nz[j];
            int gre = ttt;
            cz[++ttt] = 8;
            czx[ttt] = tx[i].wz[j + 21];
            czy[ttt] = nz[j];
            int jw1 = ttt;
            cz[++ttt] = 6;
            czx[ttt] = gre;
            czy[ttt] = jw;
            tx[i].wz[j + 21] = ttt;
            cz[++ttt] = 8;
            czx[ttt] = gre;
            czy[ttt] = jw;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = jw1;
            jw = ttt;
        }
    }

    /*for(int i=0;i<n;i++)
    {
    for(int j=0;j<=15;j++)out[i][j]=tb[i].wz[j+1];
    }
    for(int i=la+lb;i<=ttt;i++)
    {
    operations[i]=cz[i];
    operands[i][0]=czx[i];
    operands[i][1]=czy[i];
    }
    return ttt+1;*/
    for (int i = cnt; i >= 1; i--) {
        int sth = jg[i];
        cz[++ttt] = 7;
        czx[ttt] = czy[ttt] = sth;
        int fsth = ttt;
        int x1 = bx[i], x2 = by[i];

        for (int j = 1; j <= 36; j++) {
            cz[++ttt] = 8;
            czx[ttt] = tx[x1].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 8;
            czx[ttt] = tx[x2].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            int gre = ttt;
            cz[++ttt] = 8;
            czx[ttt] = tx[x1].wz[j];
            czy[ttt] = fsth;
            cz[++ttt] = 8;
            czx[ttt] = tx[x2].wz[j];
            czy[ttt] = sth;
            cz[++ttt] = 14;
            czx[ttt] = ttt - 1;
            czy[ttt] = ttt - 2;
            tx[x1].wz[j] = gre;
            tx[x2].wz[j] = ttt;
        }
    }

    /*for(int i=0;i<n;i++)
    {
    for(int j=0;j<=15;j++)out[i][j]=tb[i].wz[j+1];
    }
    for(int i=la+lb;i<=ttt;i++)
    {
    operations[i]=cz[i];
    operands[i][0]=czx[i];
    operands[i][1]=czy[i];
    }
    return ttt+1;*/
    for (int i = 1; i <= n / 2; i++) {
        swap(tx[i], tx[n + 1 - i]);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 16; j++)
            tb[i].wz[j] = tx[i].wz[j + 20];
    }

    for (int i = n + 1; i <= 1024; i++) {
        for (int j = 1; j <= 16; j++)
            tb[i].wz[j] = la + lb;
    }

    findjiaohuana(1, 1024);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 15; j++)
            out[i][j] = tb[i + 1].wz[j + 1];
    }

    for (int i = la + lb; i <= ttt; i++) {
        operations[i] = cz[i];
        operands[i][0] = czx[i];
        operands[i][1] = czy[i];
    }

    return ttt + 1;
}