#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define cout if(false) cout
#define INF 1e7
vector<int> t, a;
int n;
int tot;
void genTree(int i, int s, int e){
if(s == e){
t[i] = INF; //symbol for non-device
return;
}
t[i] = 0;
int m = (s + e)/2;
if(tot - (m-s+1) >= n){ //can prune this off
tot -= (m-s+1);
t[i*2] = INF+1; //symbol for return to start of tree
}else{
genTree(i*2, s, m);
}
genTree(i*2+1, m+1, e);
}
int num = -1, cnt = 0;
void giveNames(int i, int s, int e){
if(t[i] == INF){ //this has to be return
return;
}else if(t[i] == INF+1){
t[i] = -1; // returns to origin
return;
}
t[i] = num;
num--;
int m = (s + e)/2;
giveNames(i*2, s, m);
giveNames(i*2+1, m+1, e);
}
vector<int> states;
void sim(int i, int cnt){
//cout<<"SIMUL: "<<i<<" "<<cnt<<endl;
if(t[i] == INF){
t[i] = cnt;
return;
}else if(i != 1 && t[i] == -1){ //means do nothing
sim(1, cnt);
return;
}
if(states[i] == 0){
states[i] ^= 1;
sim(i*2, cnt);
}else{
states[i] ^= 1;
sim(i*2+1, cnt);
}
}
void create_circuit(int M, std::vector<int> A) {
n = A.size()+1;
a = A;
a.push_back(0);
//generate next power of two
tot = 1<<((int)(ceil(log2(n))));
t = vector<int>(tot*2+1, -INF);
cout<<"STARTED GEN"<<endl;
genTree(1, 0, tot-1);
cout<<"Gen"<<endl;
giveNames(1, 0, tot-1);
cout<<"Names"<<endl;
for(int i = 0; i < t.size(); i++){
cout<<i<<" "<<t[i]<<endl;
}
states = vector<int>(t.size());
for(int i = 0; i < n; i++){
// /cout<<"SIM "<<i<<endl;
sim(1, a[i]);
}
cout<<"SIMMED"<<endl;
for(int i = 0; i < states.size(); i++){
assert(states[i] == 0);
}
//so its done numbering. now need to output it
vector<int> C(M+1, -1);
int s = -num - 1;
vector<int> X(s), Y(s);
for(int i = 0; i < t.size(); i++){
if((t[i] == INF) || t[i] == INF+1 || t[i] < -s-1 || (i != 1 && t[i] == -1) || t[i] >= 0) continue;
cout<<i<<" "<<t[i]<<endl;
X[-t[i]-1] = t[i*2];
Y[-t[i]-1] = t[i*2+1];
}
cout<<"ANSWERING "<<endl;
for(int i = 0; i< C.size(); i++){
cout<<i<<" "<<C[i]<<endl;
}
for(int i = 0; i < X.size(); i++){
cout<<i<<" : "<<-i-1<<" : "<<X[i]<<" "<<Y[i]<<endl;
}
answer(C, X, Y);
cout<<"DONE"<<endl;
}
