#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;
}