#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int> g[N];
int n, m, sz, a[N];
vector<int> order, X, Y;
void build(int id){
X[id-1]=-(id<<1);
Y[id-1]=-(id<<1|1);
g[id].push_back(id<<1);
g[id].push_back(id<<1|1);
if ((id<<1)>=sz) return;
build(id<<1);
build(id<<1|1);
}
void dfs(int id){
if (g[id].empty()){
order.push_back(id);
return;
}
dfs(id<<1|a[id]);
a[id]^=1;
}
void create_circuit(int M, std::vector<int> A) {
n=A.size(), m=M;
vector<int> C(M+1);
C[0]=A[0];
for (int i=1; i<=M; ++i) C[i]=-1;
A.erase(A.begin());
A.push_back(0);
do{
A.insert(A.end()-1, -1);
}while (__builtin_popcount(A.size())!=1);
sz=A.size();
X.resize(sz-1);
Y.resize(sz-1);
build(1);
for (int i=0; i<sz; ++i) dfs(1);
for (int i=0; i<(int)A.size(); ++i){
int id=order[i];
if (id&1) Y[(id>>1)-1]=A[i];
else X[(id>>1)-1]=A[i];
}
answer(C, X, Y);
}
