#include "doll.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) begin(x),end(x)
const int oo = 1e9;
void create_circuit(int M, std::vector<int> A) {
int n = A.size();
int m = M;
vi c(m + 1);
c[0] = -1;
vi x,y;
int at=0;
bool bad=0;
auto nwnode = [&]() {
x.push_back(-oo);
y.push_back(-oo);
return at++;
};
auto swi = [&](int at) {
return -(at+1);
};
{
vvi nxt(m+1);
for(int i=0;i+1<n;++i) {
nxt[A[i]].push_back(A[i+1]);
}
nxt[A.back()].push_back(0);
nxt[0].push_back(A[0]);
auto buildseg = [&](int my, vi to) {
if(size(to)==0) {
c[my]=0;
return;
}else if(size(to)==1) {
c[my]=to[0];
return;
}else if(size(to)==2) {
int sw = nwnode();
c[my]=swi(sw);
x[sw]=to[0];
y[sw]=to[1];
} else bad=1;
};
for(int i=0;i<=m;++i) {
buildseg(i,nxt[i]);
}
}
if(bad) {
fill(all(c),-1);
x.clear();
y.clear();
at=0;
A.push_back(0);
auto buildsegtree = [&](vi dest) {
int pw=1;
int dep=0;
while(pw<dest.size()) pw*=2, dep++;
{
int last = dest.back();
dest.pop_back();
while(dest.size()+1!=pw) {
dest.push_back(swi(at));
}
dest.push_back(last);
}
vector<bool> state(pw);
x.resize(pw-1);
y.resize(pw-1);
for(int i=0;i<pw-1;++i) {
x[i] = swi(i*2+1);
y[i] = swi(i*2+2);
}
auto place = [&](auto&& self, int at, int d, int to) {
if(d==dep-1) {
if(state[at]) y[at]=to;
else x[at]=to;
state[at]=!state[at];
return;
}
self(self,at*2+1 + state[at],d+1,to);
state[at]=!state[at];
};
for(int i=0;i<pw;++i) {
place(place,0,0,dest[i]);
}
};
buildsegtree(A);
}
answer(c,x,y);
}
