#include<bits/stdc++.h>
using namespace std;
#include "abc.h"
//CHANGE THIS LINE
const int LEN=1024;
string toBin(int x,int len){
string s="";
while(x>0){
s+=((x&1)+'0');
x>>=1;
}
while(s.length()<len){
s+='0';
}
reverse(s.begin(),s.end());
return s;
}
void DFS(int u,int col[],vector<vector<int>> &graph){
for(int v:graph[u]){
if(col[v]==-1){
col[v]=(col[u]^1);
DFS(v,col,graph);
}
else{
assert(col[v]==(col[u]^1));
}
}
}
void getseq(vector<int> &p,string &s){
if(p.size()==1){
return;
}
int n=p.size();
vector<vector<int>> graph(n);
for(int i=0;i<n/2;i++){
graph[i].push_back(i+n/2);
graph[i+n/2].push_back(i);
graph[p[i]].push_back(p[i+n/2]);
graph[p[i+n/2]].push_back(p[i]);
}
int col[n];
memset(col,-1,sizeof(col));
for(int i=0;i<n;i++){
if(col[i]==-1){
col[i]=0;
DFS(i,col,graph);
}
}
vector<int> le(n/2),ri(n/2);
for(int i=0;i<n/2;i++){
s+=(col[p[i]]+'0');
if(col[p[i]]){
swap(p[i],p[i+n/2]);
}
le[i]=(p[i]%(n/2));
ri[i]=(p[i+n/2]%(n/2));
}
getseq(le,s),getseq(ri,s);
for(int i=0;i<n/2;i++){
s+=(col[i]+'0');
}
}
int alice(const int n,const char names[][5],const unsigned short numbers[],bool outputs_alice[]){
int power[5];
power[1]=0;
int breh=1;
for(int i=2;i<5;i++){
breh*=26;
power[i]=power[i-1]+breh;
}
string s="";
vector<pair<int,int>> order(LEN);
for(int i=0;i<n;i++){
int x=0;
for(int j=0;j<5;j++){
if(names[i][j]=='\0'){
x+=power[j];
break;
}
x=x*26+(names[i][j]-'a');
}
order[i]={x,i};
}
for(int i=n;i<LEN;i++){
order[i]={(1<<19)-1-(i-n),i};
}
sort(order.begin(),order.end());
vector<int> p(LEN);
for(int i=0;i<LEN;i++){
p[i]=order[i].second;
if(i<n){
s+=toBin(order[i].first,19);
s+=toBin(order[i].first,19);
if(order[i].second<n){
s+=toBin(numbers[order[i].second],16);
}
else{
s+=toBin(0,16);
}
s+=toBin(0,1);
}
}
int old=s.length();
getseq(p,s);
for(int i=0;i<s.length();i++){
if(s[i]=='1'){
outputs_alice[i]=true;
}
else{
outputs_alice[i]=false;
}
}
return s.length();
}
bool cmp(pair<pair<int,int>,int> &a,pair<pair<int,int>,int> &b){
return (a.first.second<b.first.second);
}
int bob(const int m,const char senders[][5],const char recipients[][5],bool outputs_bob[]){
int power[5];
power[1]=0;
int breh=1;
for(int i=2;i<5;i++){
breh*=26;
power[i]=power[i-1]+breh;
}
string s="";
vector<pair<pair<int,int>,int>> order(LEN);
for(int i=0;i<m;i++){
int x=0,y=0;
for(int j=0;j<5;j++){
if(senders[i][j]=='\0'){
x+=power[j];
break;
}
x=x*26+(senders[i][j]-'a');
}
for(int j=0;j<5;j++){
if(recipients[i][j]=='\0'){
y+=power[j];
break;
}
y=y*26+(recipients[i][j]-'a');
}
order[i]={{x,y},i};
}
for(int i=m;i<LEN;i++){
order[i]={{(1<<19)-1,(1<<19)-1},i};
}
sort(order.begin(),order.end(),cmp);
int val[LEN];
for(int i=0;i<order.size();i++){
val[order[i].second]=i;
}
sort(order.begin(),order.end());
vector<int> p(LEN);
for(int i=0;i<LEN;i++){
p[i]=val[order[i].second];
if(i<m){
s+=toBin(order[i].first.first,19);
s+=toBin(order[i].first.second,19);
s+=toBin(0,16);
s+=toBin(1,1);
}
}
getseq(p,s);
for(int i=0;i<s.length();i++){
if(s[i]=='1'){
outputs_bob[i]=true;
}
else{
outputs_bob[i]=false;
}
}
return s.length();
}
// you may find the definitions useful
const int OP_ZERO = 0; // f(OP_ZERO, x0, x1) = 0
const int OP_NOR = 1; // f(OP_NOR, x0, x1) = !(x0 || x1)
const int OP_GREATER = 2; // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1 = 3; // f(OP_NOT_X1, x0, x1) = !x1
const int OP_LESS = 4; // f(OP_LESS, x0, x1) = (x0 < x1)
const int OP_NOT_X0 = 5; // f(OP_NOT_X0, x0, x1) = !x0
const int OP_XOR = 6; // f(OP_XOR, x0, x1) = (x0 ^ x1)
const int OP_NAND = 7; // f(OP_NAND, x0, x1) = !(x0 && x1)
const int OP_AND = 8; // f(OP_AND, x0, x1) = (x0 && x1)
const int OP_EQUAL = 9; // f(OP_EQUAL, x0, x1) = (x0 == x1)
const int OP_X0 = 10; // f(OP_X0, x0, x1) = x0
const int OP_GEQ = 11; // f(OP_GEQ, x0, x1) = (x0 >= x1)
const int OP_X1 = 12; // f(OP_X1, x0, x1) = x1
const int OP_LEQ = 13; // f(OP_LEQ, x0, x1) = (x0 <= x1)
const int OP_OR = 14; // f(OP_OR, x0, x1) = (x0 || x1)
const int OP_ONE = 15; // f(OP_ONE, x0, x1) = 1
int tim;
const int LIMIT=2*1e7;
int Operations[LIMIT],Operands[LIMIT][2];
//int val[LIMIT];
vector<int> make(int len){
vector<int> v(len);
for(int i=0;i<len;i++){
v[i]=tim+i;
}
tim+=len;
return v;
}
int makeone(){
Operands[tim][0]=-2,Operands[tim][1]=-2,Operations[tim]=-2;
tim++;
assert(tim<=LIMIT);
return tim-1;
}
struct tup{
vector<int> u,v,w,t;
};
int eval(int x0,int x1,int p){
int temp=(p/(1<<(x0+2*x1)));
return (temp&1);
}
void init(int idx,int a,int b,int ope){
if(ope==-1){
assert(a==-1&&b==-1);
}
else{
assert(ope>=0&&ope<16&&idx>a&&idx>b&&a>=0&&b>=0);
//val[idx]=eval(val[a],val[b],ope);
}
Operands[idx][0]=a,Operands[idx][1]=b,Operations[idx]=ope;
}
/*int print(vector<int> a){
int x=0;
for(int i=0;i<a.size();i++){
x=(x*2+val[a[i]]);
}
return x;
}*/
int ZeroId,OneId;
int cmpGRE(vector<int> a,vector<int> a2,vector<int> b,vector<int> b2){
for(int i=0;i<a2.size();i++){
a.push_back(a2[i]);
}
for(int i=0;i<b2.size();i++){
b.push_back(b2[i]);
}
assert(a.size()==b.size());
int equ=OneId;
int gre=ZeroId;
for(int i=0;i<a.size();i++){
int cmp1=makeone();
init(cmp1,a[i],b[i],OP_GREATER);
int cmp2=makeone();
init(cmp2,a[i],b[i],OP_EQUAL);
int tmp=makeone();
init(tmp,equ,cmp1,OP_AND);
int nxtGre=makeone();
init(nxtGre,gre,tmp,OP_OR);
int nxtEqu=makeone();
init(nxtEqu,equ,cmp2,OP_AND);
equ=nxtEqu,gre=nxtGre;
}
return gre;
}
vector<int> opeAND(vector<int> &a,int b){
vector<int> nxt(a.size());
for(int i=0;i<a.size();i++){
nxt[i]=makeone();
init(nxt[i],a[i],b,OP_AND);
}
return nxt;
}
vector<int> opeOR(vector<int> &a,vector<int> &b){
assert(a.size()==b.size());
vector<int> nxt(a.size());
for(int i=0;i<a.size();i++){
nxt[i]=makeone();
init(nxt[i],a[i],b[i],OP_OR);
}
return nxt;
}
vector<int> opeXOR(vector<int> &a,vector<int> &b){
assert(a.size()==b.size());
vector<int> nxt(a.size());
for(int i=0;i<a.size();i++){
nxt[i]=makeone();
init(nxt[i],a[i],b[i],OP_XOR);
}
return nxt;
}
void swapCond(vector<int> &a,vector<int> &b,int cond){
assert(a.size()==b.size());
vector<int> c=opeXOR(a,b);
c=opeAND(c,cond);
a=opeXOR(a,c),b=opeXOR(b,c);
}
void mergeSort(vector<tup> &curr,int x,int y,int d,vector<int> &record){
if(x+d==y){
int cond=cmpGRE(curr[x].u,curr[x].t,curr[y].u,curr[y].t);
record.push_back(cond);
swapCond(curr[x].u,curr[y].u,cond);
swapCond(curr[x].v,curr[y].v,cond);
swapCond(curr[x].w,curr[y].w,cond);
swapCond(curr[x].t,curr[y].t,cond);
return;
}
mergeSort(curr,x,y,2*d,record),mergeSort(curr,x+d,y+d,2*d,record);
for(x=x+d;x+d<curr.size();x+=2*d){
y=x+d;
int cond=cmpGRE(curr[x].u,curr[x].t,curr[y].u,curr[y].t);
record.push_back(cond);
swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
}
}
void undo(vector<tup> &curr,int X,int Y,int d,vector<int> &record){
if(X+d==Y){
int x=X,y=Y;
assert(!record.empty());
int cond=record.back();
record.pop_back();
swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
return;
}
vector<pair<int,int>> bruh;
for(int x=X+d;x+d<curr.size();x+=2*d){
bruh.push_back({x,x+d});
}
for(int i=bruh.size()-1;i>=0;i--){
int x=bruh[i].first,y=bruh[i].second;
assert(!record.empty());
int cond=record.back();
record.pop_back();
swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
}
undo(curr,X+d,Y+d,2*d,record);
undo(curr,X,Y,2*d,record);
}
void bijec(int l,int r,vector<tup> &curr,vector<int> &record){
if(l==r){
return;
}
int mid=((l+r)>>1);
for(int x=l;x<=mid;x++){
int y=x-l+mid+1;
assert(!record.empty());
int cond=record.back();
record.pop_back();
swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
}
bijec(l,mid,curr,record);
bijec(mid+1,r,curr,record);
for(int x=l;x<=mid;x++){
int y=x-l+mid+1;
assert(!record.empty());
int cond=record.back();
record.pop_back();
swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
}
}
vector<int> opeADD(vector<int> &a,vector<int> &b){
assert(a.size()==b.size());
vector<int> rem(a.size()),res(a.size());
rem[a.size()-1]=ZeroId;
for(int i=a.size()-1;i>=0;i--){
int tmp=makeone();
init(tmp,a[i],b[i],OP_XOR);
res[i]=makeone();
init(res[i],tmp,rem[i],OP_XOR);
if(i>0){
int tmp2=makeone();
init(tmp2,tmp,rem[i],OP_AND);
tmp=makeone();
init(tmp,a[i],b[i],OP_AND);
rem[i-1]=makeone();
init(rem[i-1],tmp,tmp2,OP_OR);
}
}
return res;
}
int circuit(const int la,const int lb,int operations[],int operands[][2],int outputs_circuit[][16]){
for(int i=0;i<la+lb;i++){
init(i,-1,-1,-1);
}
string breh="";
vector<int> permu(LEN);
for(int i=0;i<LEN;i++){
permu[i]=i;
}
getseq(permu,breh);
const int counter=19+19+16+1;
int n=(la-breh.length())/counter,m=(lb-breh.length())/counter;
vector<tup> curr(2*LEN);
for(int i=0;i<2*LEN;i++){
curr[i].u.resize(19),curr[i].v.resize(19),curr[i].w.resize(16),curr[i].t.resize(1);
}
tim=0;
for(int i=0;i<n;i++){
for(int j=0;j<19;j++){
curr[i].u[j]=tim+j,curr[i].v[j]=tim+19+j;
if(j<16){
curr[i].w[j]=tim+38+j;
}
if(j==0){
curr[i].t[j]=tim+54+j;
}
}
tim+=counter;
}
tim=la;
for(int i=LEN;i<LEN+m;i++){
for(int j=0;j<19;j++){
curr[i].u[j]=tim+j,curr[i].v[j]=tim+19+j;
if(j<16){
curr[i].w[j]=tim+38+j;
}
if(j==0){
curr[i].t[j]=tim+54+j;
}
}
tim+=counter;
}
tim=la+lb;
OneId=makeone();
init(OneId,0,1,OP_ONE);
ZeroId=makeone();
init(ZeroId,0,1,OP_ZERO);
for(int i=n;i<LEN;i++){
int x=(1<<19)-1-(i-n);
for(int j=0;j<19;j++){
if(x&(1<<(18-j))){
curr[i].u[j]=OneId;
curr[i].v[j]=OneId;
}
else{
curr[i].u[j]=ZeroId;
curr[i].v[j]=ZeroId;
}
if(j<16){
curr[i].w[j]=ZeroId;
if(j==0){
curr[i].t[j]=ZeroId;
}
}
}
}
for(int i=LEN+m;i<2*LEN;i++){
int x=(1<<19)-1;
for(int j=0;j<19;j++){
if(x&(1<<(18-j))){
curr[i].u[j]=OneId;
curr[i].v[j]=OneId;
}
else{
curr[i].u[j]=ZeroId;
curr[i].v[j]=ZeroId;
}
if(j<16){
curr[i].w[j]=ZeroId;
if(j==0){
curr[i].t[j]=OneId;
}
}
}
}
vector<int> record;
int OLD=tim;
mergeSort(curr,0,LEN,1,record);
vector<int> sum(16);
for(int i=0;i<sum.size();i++){
sum[i]=ZeroId;
}
for(int i=0;i<curr.size();i++){
if(i>0){
int cond=cmpGRE(curr[i].u,{},curr[i-1].u,{});
int inv=makeone();
init(inv,0,cond,OP_NOT_X1);
sum=opeAND(sum,inv);
}
sum=opeOR(sum,curr[i].w);
curr[i].w=sum;
}
undo(curr,0,LEN,1,record);
for(int i=la+counter*m;i<la+lb;i++){
record.push_back(i);
}
reverse(record.begin(),record.end());
bijec(LEN,2*LEN-1,curr,record);
for(int i=0;i<curr.size();i++){
swap(curr[i].u,curr[i].v);
}
mergeSort(curr,0,LEN,1,record);
for(int i=0;i<curr.size();i++){
swap(curr[i].u,curr[i].v);
}
sum.clear(),sum.resize(16);
for(int i=0;i<sum.size();i++){
sum[i]=ZeroId;
}
for(int i=curr.size()-1;i>=0;i--){
if(i+1<curr.size()){
int cond=cmpGRE(curr[i+1].v,{},curr[i].v,{});
int inv=makeone();
init(inv,0,cond,OP_NOT_X1);
sum=opeAND(sum,inv);
}
vector<int> old=curr[i].w;
curr[i].w=sum;
sum=opeADD(sum,old);
}
undo(curr,0,LEN,1,record);
for(int i=counter*n;i<la;i++){
record.push_back(i);
}
reverse(record.begin(),record.end());
bijec(0,LEN-1,curr,record);
assert(tim<=LIMIT);
for(int i=0;i<tim;i++){
operands[i][0]=Operands[i][0],operands[i][1]=Operands[i][1];
operations[i]=Operations[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<16;j++){
outputs_circuit[i][15-j]=curr[i].w[j];
}
}
return tim;
}
