#include "doll.h"
#include <bits/stdc++.h>
#define N 300005
using namespace std;
int x[N],y[N];
bool last[N];
int add;
void solve(int now,int needed,int num){
//cout << now << " " << needed << " " << num << endl;
assert(needed);
if(num == 2){
if(needed == 1){
y[now] = -2;
x[now] = 1e9;
}
if(needed == 2){
x[now] = 1e9;
y[now] = 1e9;
}
return;
}
int nwlen = num/2;
add++;
y[now] = -add;
solve(add,min(needed,nwlen),nwlen);
needed -= min(needed,nwlen);
if(needed == 0){
x[now] = -2;
}
else{
add++;
x[now] = -add;
solve(add,min(needed,nwlen),nwlen);
}
}
void create_circuit(int M, vector<int> A) {
int n = A.size();
vector<int> C(M + 1);
C[0] = A[0];
for (int i = 1; i <= M; ++i) {
C[i] = -1;
}
if(n == 1){
C[A[0]] = 0;
answer(C, {0}, {0});
return;
}
A.push_back(0);
x[2] = -2;
y[2] = -1;
int num = 1;
while(num < n)
num *= 2;
add = 2;
solve(1,n,num);
int cnt = 0;
int pos = 0;
while(cnt < n){
//cout << pos << endl;
if(pos >= 0){
pos = C[pos];
}
else{
pos *= -1;
if(last[pos] == 0){
last[pos] = 1;
if(x[pos] == 1e9){
cnt++;
x[pos] = A[cnt];
}
pos = x[pos];
}
else{
last[pos] = 0;
if(y[pos] == 1e9){
cnt++;
y[pos] = A[cnt];
}
pos = y[pos];
}
}
}
vector<int> X,Y;
for(int i = 1;i<=add;i++){
X.push_back(x[i]);
Y.push_back(y[i]);
}
// for(auto u:C){
// cout << u << " ";
// }
// cout << endl;
// for(auto u:X){
// cout << u << " ";
// }
// cout << endl;
// for(auto u:Y){
// cout << u << " ";
// }
// cout << endl;
answer(C,X,Y);
}
