#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> order;
namespace sim{
int M, N;
std::vector<int> A;
bool answered;
int S;
std::vector<int> IC, IX, IY;
void simulate() {
int P = 0;
std::vector<bool> state(S + 1, false);
int pos = IC[0];
int k = 0;
for (;;) {
//cout<<pos<<endl;
if (pos < 0) {
state[-pos] = !state[-pos];
pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
} else {
if (pos == 0) {
break;
}
//cout<<pos<<'\n';
if (pos>=1){
order.push_back(pos);
}
pos = IC[pos];
}
}
}
}
vector<vector<int>> adjlist;
vector<int> exitto;
vector<int> switchxto;
vector<int> switchyto;
int sind = 0;
// level 0 -- base
//int lind = -1;
int finale = 0;
int ind = 1;
int create(int parent, int level, int num, const vector<int> &seq, int s, int e){
// returns index of switch
/*cout<<"make switch "<<-1-sind<<" at level "<<level<<'\n'<<" with num "<<num<<'\n';
for (int i : seq){
cout<<i<<' ';
}cout<<'\n';*/
/*cout<<seq.size()<<'\n';*/
if (num==0){
//cout<<"num is 0"<<'\n';
if (level==0){
return (e==finale)?0:-1;
}
// make something that counts (1<<level) times before returning
int firstswitch = sind;
for (int i = 0; i<level-1; i++){
// make switch
// parent: prevconnect
// x: -1
// y: sind+1
switchxto.push_back(1e9);
switchyto.push_back(1e9);
switchxto[sind]=-1;
switchyto[sind]=-1-(sind+1);
sind++;
}
switchxto.push_back(1e9);
switchyto.push_back(1e9);
switchxto[sind]=-1;
switchyto[sind]=(e==finale)?0:-1;
//lind=sind;
sind++;
return -1-firstswitch;
}
if (level==0){
//numleft--;
ind++;
return ind-1;
}
int switchtouse = sind;
switchxto.push_back(1e9);
switchyto.push_back(1e9);
sind++;
int sendleft = min((1<<(level-1)),num);
int sendright = max(0,num-(1<<(level-1)));
vector<int> left;
vector<int> right;
int ptr = 0;
for (int i = 0; i<sendright; i++){
left.push_back(seq[ptr]);
right.push_back(seq[ptr+1]);
ptr+=2;
}
for (int i = sendright; i<sendleft; i++){
left.push_back(seq[ptr]);
ptr++;
}
int cl = create(switchtouse,level-1,sendleft,left,s,(s+e)/2);
int cr = create(switchtouse,level-1,sendright,right,(s+e)/2+1,e);
switchxto[switchtouse]=cl;
switchyto[switchtouse]=cr;
return -1-switchtouse;
}
void create_circuit(int m, std::vector<int> a) {
int n = a.size();
if (n%2!=1){
n++;
}
int level = log2(n-1)+1;
finale = (1<<level)-1;
create(0,level,a.size(),a,0,(1<<level)-1);
/*if (lind!=-1){
switchyto[lind]=0;
}*/
exitto.resize(n+1,-1);
sim::IC = exitto;
sim::IX = switchxto;
sim::IY = switchyto;
sim::simulate();
/*for (int i : order){
cout<<i<<' ';
}cout<<'\n';*/
vector<int> ord2ind(order.size()+1);
for (int i = 0; i<order.size(); i++){
ord2ind[order[i]]=i;
}
for (int i = 0; i<switchxto.size(); i++){
if (switchxto[i]>=1){
switchxto[i]=a[ord2ind[switchxto[i]]];
}
if (switchyto[i]>=1){
switchyto[i]=a[ord2ind[switchyto[i]]];
}
}
exitto.resize(m+1,-1);
/*for (int i : switchxto){
cout<<i<<' ';
}cout<<'\n';
for (int i : switchyto){
cout<<i<<' ';
}cout<<'\n';*/
answer(exitto,switchxto,switchyto);
}
