#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, int> exits[400005];
vector<int> X, Y, C;
bool stateIsX[400005];
int depth[400005];
int switchIdx = -1;
set<pair<int, int>> notSetToX;
void build(int cur, int par, int add) {
if(cur > 0) {
--switchIdx;
if(X[-(par+1)] == cur) X[-(par+1)] = switchIdx;
else Y[-(par+1)] = switchIdx;
X.push_back(cur);
Y.push_back(add);
depth[-(switchIdx+1)] = depth[-(par+1)]+1;
stateIsX[-(switchIdx+1)] = 1;
return;
}
stateIsX[-(cur+1)] = !stateIsX[-(cur+1)];
build(!stateIsX[-(cur+1)]?X[-(cur+1)]:Y[-(cur+1)], cur, add);
}
void resetAll(int cur, int par) {
if(cur == 0) return;
if(cur > 0) {
--switchIdx;
int add = notSetToX.begin()->second;
// cerr << notSetToX.begin()->first << endl;
notSetToX.erase(notSetToX.begin());
if(X[-(par+1)] == cur) X[-(par+1)] = switchIdx;
else Y[-(par+1)] = switchIdx;
X.push_back(cur);
Y.push_back(add);
depth[-(switchIdx+1)] = depth[-(par+1)]+1;
stateIsX[-(switchIdx+1)] = 1;
resetAll(add, 0);
return;
}
if(stateIsX[-(cur+1)]) notSetToX.insert({depth[-(cur+1)], cur});
else notSetToX.erase({depth[-(cur+1)], cur});
stateIsX[-(cur+1)] = !stateIsX[-(cur+1)];
resetAll(!stateIsX[-(cur+1)]?X[-(cur+1)]:Y[-(cur+1)], cur);
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
if(N == 1) {
answer({A[0], 0}, {}, {});
return;
}
C.assign(M+1, -1);
X.push_back(A[0]);
Y.push_back(A[1]);
stateIsX[0] = 1;
for(int i = 2; i < A.size(); i++) {
build(-1, 0, A[i]);
}
for(int i = -1; i >= switchIdx; i--) {
notSetToX.insert({depth[-(i+1)], i});
}
notSetToX.insert({1<<30, 0});
resetAll(-1, 0);
// vector<int> C(M + 1);
// C[0] = -1;
// for (int i = 1; i <= M; ++i) {
// C[i] = -1;
// }
// for(auto x: A[i]) {
// build(-1, add);
// }
//
// for(int i = -1; i >= switchIdx; i--) {
// X.push_back(exits[-(i+1)].first);
// Y.push_back(exits[-(i+1)].second);
// cerr << i << ": " << X[-(i+1)] << " " << Y[-(i+1)] << " " << stateIsX[-(i+1)] << endl;
// }
// cerr << N << " -> " << X.size() << " (" << N + log2(N) << ")" << endl;
// double score;
// if(X.size() <= N + log2(N)) score = 100;
// else if(X.size() > 2*N) score = 0;
// else score = 100*(0.5 + 0.4 * ( (2*N - X.size()) / (N - log2(N)) ) * ( (2*N - X.size()) / (N - log2(N)) ));
// cerr << "Score: " << score << endl;
// for(int i = 0; i < C.size(); i++)
// cout << i << " " << C[i] << endl;
// for(int i = 0; i < X.size(); i++) {
// cout << -(i+1) << " " << X[i] << endl;
// cout << -(i+1) << " " << Y[i] << endl;
// }
answer(C, X, Y);
// cout << M << endl;
// for(auto x: A)
// cout << x << endl;
}
