#include "doll.h"
#include <bits/stdc++.h>
#define uwu return
using namespace std;
vector <int> X, Y;
const int TEMP1 = 712271227, TEMP2 = 1e9 + 7;
int build_cbt(int N, int d){
if(d == 0)
return TEMP1;
int l, r;
if (N <= (1 << (d - 1)))
r = build_cbt(N, d - 1), l = TEMP2;
else
r = build_cbt((1 << (d - 1)), d - 1), l = build_cbt(N - (1 << (d - 1)), d - 1);
X.push_back(l);
Y.push_back(r);
uwu - ((int)X.size());
}
const int SIZE = 2e5 + 5;
vector <int> tmpA;
bitset <SIZE> status;
int cnt = 0, head;
void simulate(int id){
if(cnt >= (int)tmpA.size())
uwu;
int rid = (-id) - 1;
status[rid] = !status[rid];
if (status[rid]){
if(X[rid] == TEMP1){
X[rid] = tmpA[cnt];
cnt++;
simulate(head);
uwu;
}
else if(X[rid] == TEMP2){
X[rid] = head;
simulate(head);
uwu;
}
simulate(X[rid]);
uwu;
}
else{
if(Y[rid] == TEMP1){
Y[rid] = tmpA[cnt];
cnt++;
simulate(head);
uwu;
}
else if(Y[rid] == TEMP2){
Y[rid] = head;
simulate(head);
uwu;
}
simulate(Y[rid]);
uwu;
}
uwu;
}
void create_circuit(int M, vector<int> A) {
vector<int> C(M + 1);
A.push_back(0);
tmpA = A;
int N = A.size();
int d = __lg(N - 1) + 1;
X.clear(), Y.clear();
int id = build_cbt(N, d);
C[0] = id;
for (int i = 1; i <= M; ++i) {
C[i] = id;
}
head = id;
cnt = 0;
status.reset();
simulate(head);
assert(status.count() == 0);
answer(C, X, Y);
uwu;
}
