#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int> g[N];
int n, m, p, a[N];
vector<int> order, X, Y;
int mxdep;
void build(int u, int dep){
if (p==0){
g[u]={1, 1};
X[u]=Y[u]=-1;
return;
}
if (dep==mxdep){
g[u]={-1, -1};
p-=2;
return;
}
if (p){
g[u].push_back(X.size());
X.push_back(0); Y.push_back(0);
build(g[u][0], dep+1);
}else{
g[u].push_back(1);
}
if (p){
g[u].push_back(X.size());
X.push_back(0); Y.push_back(0);
build(g[u][1], dep+1);
}else{
g[u].push_back(1);
}
swap(g[u][0], g[u][1]);
X[u]=-g[u][0], Y[u]=-g[u][1];
}
void dfs(int u){
a[u]^=1;
int v=g[u][a[u]^1];
if (v==-1){
order.push_back(u<<1|(a[u]^1));
return;
}
if (v==1) return;
dfs(g[u][a[u]^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(-1);
if ((int)A.size()&1) A.push_back(-1);
A.back()=0;
n=A.size();
while ((1<<mxdep)<n) ++mxdep;
X.resize(2); Y.resize(2);
p=n;
build(1, 1);
for (int i=0; i<(1<<mxdep); ++i){
dfs(1);
}
for (int i=0; i<(int)A.size(); ++i){
int id=order[i];
if (id&1) Y[id>>1]=A[i];
else X[id>>1]=A[i];
}
X.erase(X.begin()); Y.erase(Y.begin());
answer(C, X, Y);
}
