#include "doll.h"
#include<bits/stdc++.h>
#pragma GCC optimize ("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, pii> pi4;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", "; cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()
const int inf=1000001000; // 1e9
const ll INF=10000000010000000ll; // 1e16
const int mod=1000000007;
const int MAXN=300010, LOG=18;
int n, m, k, S;
vi C, X, Y;
vi shit[MAXN];
map<vi, int> mp;
int Build(vi vec){
if (SZ(vec)==1){
return vec[0];
}
if (mp.find(vec)!=mp.end()) return mp[vec];
int v=++S;
X.pb(inf);
Y.pb(inf);
vector<int> vec0, vec1;
if (SZ(vec)&1) vec0.pb(-v);
for (int x:vec){
if (SZ(vec0)==SZ(vec1)) vec0.pb(x);
else vec1.pb(x);
}
int x=Build(vec0);
int y=Build(vec1);
X[v-1]=x;
Y[v-1]=y;
mp[vec]=-v;
return -v;
}
void create_circuit(int _m, vi A){
m=_m;
n=SZ(A);
for (int i=1; i<n; i++) shit[A[i-1]].pb(A[i]);
shit[A.back()].pb(0);
C.resize(m+1, 0);
C[0]=A[0];
for (int i=1; i<=m; i++) if (shit[i].size()) C[i]=Build(shit[i]);
answer(C, X, Y);
}
