#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 2e5+100, M = 5010, K = 22;
vi go[N];
void create_circuit(int m, std::vector<int> A) {
int n = A.size();
for(int i = 0; i < n; ++i){
go[A[i]].pb(i + 1 == n ? 0 : A[i + 1]);
}
if(n == 1){
vi X, Y, C;
C.resize(m + 1);
C[0] = A[0];
C[A[0]] = 0;
answer(C, X, Y);
return;
}
vi C(m + 1);
vi X(n * 2 + 30, N), Y(n * 2 + 30, N);
int sz = 1;
while((1<<sz) < n) ++sz;
vector<vi> layer(sz + 1);
int cnt = 1;
for(int j = 0; j <= sz; ++j){
for(int i = 0; i < (1<<j); ++i) layer[j].pb(cnt++);
}
vi dp(cnt + 5);
for(int j = cnt-1; j >= cnt-n; --j) dp[j] = 1;
for(int j = cnt-n-1; j >= 1; --j){
dp[j] = (j * 2 < cnt ? dp[j * 2] : 0) + (j * 2 + 1 < cnt ? dp[j * 2 + 1] : 0);
}
// for(int j = 1; j < cnt; ++j) cerr << j << ' ' << dp[j] << " crap\n";
// some will be zero, we will erase those...
C[0] = A[0];
for(int j = 0; j < n; ++j) C[A[j]] = -layer[0][0];
vector<pii> av;
for(int j = cnt-1; j >= cnt-n; --j){
int val = 0;
// cerr << j << ' ' << ' ' << sz;
for(int i = 0; i <= sz; ++i) val += ((1<<i)&(j-(1<<(sz)))) ? (1<<(sz-i)) : 0;
av.pb({val, j});
}
sort(all(av));
vector<bool> dead(cnt, 0);
for(int j = 1; j * 2 + 2 < cnt; ++j){
if(dead[j]) continue;
// cerr << j << ' ';
if(dp[j * 2] == 0){
dead[j * 2] = 1;
X[j - 1] = -layer[0][0];
}else{
X[j - 1] = - 2 * j;
}
Y[j - 1] = - 2 * j - 1;
}
A.pb(0);
for(int i = 0; i < n; ++i){
int x = av[i].ss;
// cerr << x << ' ';
if(x % 2) Y[x/2-1] = A[i+1];
else X[x/2-1] = A[i+1];
}
// we gotta compress things
vector<array<int, 3>> used;
vi id(X.size());
for(int i = 0; i < X.size(); ++i){
if(X[i] != N){
used.pb({i, X[i], Y[i]});
id[i + 1] = used.size();
}
}
vi xx, yy;
for(int i = 0; i < (int)used.size(); ++i){
if(used[i][1] >= 0){
xx.pb(used[i][1]);
}else{
xx.pb(-id[-used[i][1]]);
}
if(used[i][2] >= 0){
yy.pb(used[i][2]);
}else{
yy.pb(-id[-used[i][2]]);
}
}
for(int &x: C){
if(x >= 0) x = x;
else x = -id[-x];
}
// X.resize(cnt);
// Y.resize(cnt);
// for(int x: xx) cerr << x << ' '; cerr << '\n';
// for(int x: yy) cerr << x << ' '; cerr << '\n';
// for(int x: C) cerr << x << ' '; cerr << '\n';
answer(C, xx, yy);
}
