#include "doll.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX = 1e6 + 1;
vector <vector <int> > g(NMAX);
int cur = 1;
void build(int v, int l, int r, int st, int fin){
if(l == r){
if(r == fin){
g[v].pb(v);
g[v].pb(0);
return;
}
g[v].pb(1);
return;
}
int m = (l + r) / 2;
if(m < st || m > fin){
g[v].pb(1);
cur++;
g[v].pb(cur);
build(cur, m + 1, r, st, fin);
}
else{
cur++;
g[v].pb(cur);
build(cur, l, m, st, fin);
cur++;
g[v].pb(cur);
build(cur, m + 1, r, st, fin);
}
}
vector <int> trav;
vector <int> state(NMAX, 1);
void traverse(int v, int x){
if(trav.size() == x) return;
if(g[v].size() == 1){
trav.pb(v);
traverse(g[v][0], x);
}
else{
state[v] ^= 1;
traverse(g[v][state[v]], x);
}
}
vector <int> ind(NMAX);
vector <int> c, X, Y;
void create_circuit(int M, std::vector<int> A) {
c.resize(M + 1);
int n = A.size();
int x = log2(n);
if(__builtin_popcount(n) > 1) x++;
build(1, 1, (1 << x), (1 << x) - n + 1, (1 << x));
traverse(1, n - 1);
c[A[0]] = -1;
c[0] = A[0];
for(int i = 0; i < trav.size(); i++){
//cout << trav[i];
ind[trav[i]] = A[i + 1];
}
int cc = -1;
for(int i = 1; i <= cur; i++){
if(g[i].size() >= 2){
ind[i] = cc--;
}
}
X.resize((int)abs(cc + 1));
Y.resize((int)abs(cc + 1));
for(int i = 1; i <= cur; i++){
if(g[i].size() == 1){
c[ind[i]] = ind[g[i][0]];
}
else{
X[-ind[i] - 1] = ind[g[i][0]];
Y[-ind[i] - 1] = ind[g[i][1]];
}
}
/*for(int to : c){
cout << to << ' ';
}
cout << "\n";
for(int i = 0; i < X.size(); i++){
cout << X[i] << ' ' << Y[i] << "\n";
}*/
answer(c, X, Y);
}
