#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;
}
/*const int MAX_LA = 100000;
const int MAX_LB = 100000;
const int MAX_L = 20000000;
void fatal(const string& msg) {
cerr << msg << endl;
exit(1);
}
void ensureImpl(bool condition, const char* conditionStr) {
if (condition)
return;
fatal("Condition does not satisfy: " + string(conditionStr));
}
#define ensure(x...) ensureImpl(x, #x)
template <typename F>
void timed(const string& name, const F& func) {
cerr << "Running " << name << "..." << endl;
auto start = chrono::high_resolution_clock::now();
func();
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::nanoseconds>(end - start);
cerr << name << " took " << fixed << setprecision(6) << (double) duration.count() / 1e9 << " seconds" << endl;
}
int main() {
// ==================== Read Input ====================
int n, m;
cin >> n >> m;
ensure(0 <= n && n <= 700);
ensure(0 <= m && m <= 1000);
auto readUshort = [&]() {
string s;
cin >> s;
stringstream ss(s);
unsigned short x;
ss >> x;
if (s != to_string(x))
fatal("Invalid input for unsigned short: " + s);
return x;
};
vector<pair<string, unsigned short>> students;
map<string, unsigned short> studentsMap;
for (int i = 0; i < n; i++) {
string name;
cin >> name;
if (name.empty())
fatal("Expected name");
if (name.size() > 4)
fatal("Name too long: " + name);
bool ok = true;
for (char c : name)
if (c < 'a' || c > 'z')
ok = false;
if (!ok)
fatal("Invalid name: " + name);
unsigned short number = readUshort();
students.emplace_back(name, number);
if (studentsMap.count(name))
fatal("Duplicate name: " + name);
studentsMap[name] = number;
}
auto readExistingName = [&] {
string name;
cin >> name;
if (!studentsMap.count(name))
fatal("Unknown name in Bob's input: " + name);
return name;
};
vector<pair<string, string>> messages;
for (int i = 0; i < m; i++) {
string sender = readExistingName();
string recipient = readExistingName();
messages.emplace_back(sender, recipient);
}
// ==================== Call Alice ====================
char (*aliceNames)[5] = new char[n][5];
memset(aliceNames[0], 0, n * 5);
unsigned short* aliceNumbers = new unsigned short[n];
bool* aliceOutputs = new bool[MAX_LA];
memset(aliceOutputs, 0, MAX_LA);
for (int i = 0; i < n; i++) {
strcpy(aliceNames[i], students[i].first.c_str());
aliceNumbers[i] = students[i].second;
}
int la;
timed("Alice", [&]() {
la = alice(n, aliceNames, aliceNumbers, aliceOutputs);
});
for(int i=0;i<la;i++){
if(aliceOutputs[i]){
val[i]=1;
}
else{
val[i]=0;
}
}
cerr << "la = " << la << endl;
ensure(0 <= la && la <= MAX_LA);
// ==================== Call Bob ====================
char (*bobSenders)[5] = new char[m][5];
memset(bobSenders[0], 0, m * 5);
char (*bobRecipients)[5] = new char[m][5];
memset(bobRecipients[0], 0, m * 5);
bool* bobOutputs = new bool[MAX_LB];
memset(bobOutputs, 0, MAX_LB);
for (int i = 0; i < m; i++) {
strcpy(bobSenders[i], messages[i].first.c_str());
strcpy(bobRecipients[i], messages[i].second.c_str());
}
int lb;
timed("Bob", [&]() {
lb = bob(m, bobSenders, bobRecipients, bobOutputs);
});
for(int i=0;i<lb;i++){
if(bobOutputs[i]){
val[la+i]=1;
}
else{
val[la+i]=0;
}
}
cerr << "lb = " << lb << endl;
ensure(0 <= lb && lb <= MAX_LB);
// ==================== Call Circuit ====================
int* circuitOperations = new int[MAX_L];
memset(circuitOperations, 0xff, MAX_L * sizeof(int));
int (*circuitOperands)[2] = new int[MAX_L][2];
memset(circuitOperands[0], 0xff, MAX_L * 2 * sizeof(int));
int (*circuitOutputs)[16] = new int[n][16];
memset(circuitOutputs[0], 0xff, n * 16 * sizeof(int));
int l;
timed("Circuit", [&]() {
l = circuit(la, lb, circuitOperations, circuitOperands, circuitOutputs);
});
cerr << "l = " << l << endl;
ensure(0 <= l && l <= MAX_L);
bool* values = new bool[l];
memcpy(values, aliceOutputs, la * sizeof(bool));
memcpy(values + la, bobOutputs, lb * sizeof(bool));
for (int i = la + lb; i < l; i++) {
int op = circuitOperations[i];
if (op < 0 || op > 15)
fatal("Invalid operation: " + to_string(op) + " at Circuit index " + to_string(i));
int a = circuitOperands[i][0];
int b = circuitOperands[i][1];
if (a < 0 || a >= i)
fatal("Invalid operand 0: " + to_string(a) + " at Circuit index " + to_string(i));
if (b < 0 || b >= i)
fatal("Invalid operand 1: " + to_string(b) + " at Circuit index " + to_string(i));
bool x0 = values[a];
bool x1 = values[b];
values[i] = op >> (x0 + 2 * x1) & 1;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < 16; j++)
if (circuitOutputs[i][j] < 0 || circuitOutputs[i][j] >= l)
fatal("Invalid output: " + to_string(circuitOutputs[i][j]) + " at Circuit index " + to_string(i) + ", " + to_string(j));
vector<unsigned short> answers;
for (int i = 0; i < n; i++) {
unsigned short ans = 0;
for (int j = 0; j < 16; j++)
ans |= (unsigned short) values[circuitOutputs[i][j]] << j;
answers.push_back(ans);
}
// ==================== Calculate Reference Answer ====================
map<string, unsigned short> referenceMap;
for (int i = 0; i < m; i++)
referenceMap[messages[i].second] += studentsMap[messages[i].first];
bool ok = true;
for (int i = 0; i < n; i++)
if (answers[i] != referenceMap[students[i].first]) {
ok = false;
cerr << "Wrong answer for " << students[i].first << ": expected " << referenceMap[students[i].first] << ", but got " << answers[i] << endl;
exit(-1);
}
if (ok)
cerr << "Your answer seems correct" << endl;
// ==================== Print Answer ====================
for (int i = 0; i < n; i++)
cout << answers[i] << '\n';
return 0;
}*/
