#include<bits/stdc++.h>
#define st first
#define nd second
#define pii pair<int, int>
#include "doll.h"
using namespace std;
const int MAXN =4e5+5;
int n, base=1, e[2*MAXN][2], rep[2*MAXN];
bool turn[2*MAXN];
void get_edges(int id, int l, int r) {
if(l==r) {
if((base-l) * 2 >= n) {
e[id][1]=1;
}
if((base-l) * 2 + 1 >= n) {
e[id][0]=1;
}
return;
}
int m = (l+r)/2;
e[id][0] = id*2;
e[id][1] = id*2+1;
if((base-r) * 2 >= n) {
e[id][1]=1;
}
if((base-m) * 2 >= n) {
e[id][0]=1;
}
if(e[id][0]==id*2) {
get_edges(id*2, l, m);
}
if(e[id][1]==id*2+1) {
get_edges(id*2+1, m+1, r);
}
}
void simulate(int id, int v) {
int nxt = e[id][turn[id]];
turn[id] ^= 1;
if(!nxt) {
e[id][!turn[id]]=-v;
return;
}
simulate(nxt, v);
}
void create_circuit(int m, vector<int> a) {
vector<int> c(m+1);
c[0]=a[0];
a.push_back(0);
a.erase(a.begin());
n = a.size();
for(int i=1; i<=m; ++i) {
c[i]=-1;
}
while(base < n) {
base *= 2;
}
get_edges(1, 1, base);
for(int i: a) {
simulate(1, i);
}
int nr = 0;
for(int i=1; i<2*base; ++i) {
if(e[i][0]!=0 || e[i][1]!=0) {
rep[i]=++nr;
}
}
vector<int> x(nr), y(nr);
for(int i=1; i<2*base; ++i) {
if(rep[i]!=0) {
if(e[i][0]<=0) {
x[rep[i]-1]=-e[i][0];
}
else {
x[rep[i]-1]=-rep[e[i][0]];
}
if(e[i][1]<=0) {
y[rep[i]-1]=-e[i][1];
}
else {
y[rep[i]-1]=-rep[e[i][1]];
}
}
}
answer(c, x, y);
}
