#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
vector<int> g[N];
int n, m;
void create_circuit(int M, std::vector<int> A) {
n=A.size(), m=M;
for (int i=1; i<n; ++i) g[A[i-1]].push_back(A[i]);
g[0].push_back(A[0]);
g[A[n-1]].push_back(0);
for (int i=0; i<=m; ++i) if (g[i].size()){
int pw=1;
while ((int)g[i].size()%(pw*2)==0) pw*=2;
bool check=1;
for (int j=0; j<(int)g[i].size(); ++j) check&=g[i][j]==g[i][j%pw];
assert(check);
g[i].resize(pw);
}
int cur=0;
vector<int> C(M+1), X, Y;
for (int i=0; i<=m; ++i) if ((int)g[i].size()){
if ((int)g[i].size()==1){
C[i]=g[i][0];
continue;
}
cur=X.size();
C[i]=-cur-1;
X.resize((int)X.size()+(int)g[i].size()-1);
Y.resize((int)Y.size()+(int)g[i].size()-1);
auto build=[&](auto &&self, int id){
if ((id<<1)>=(int)g[i].size()){
X[cur+id-1]=g[i][(id<<1)-(int)g[i].size()];
Y[cur+id-1]=g[i][(id<<1|1)-(int)g[i].size()];
return;
}
X[cur+id-1]=-cur-(id<<1);
Y[cur+id-1]=-cur-(id<<1|1);
self(self, id<<1);
self(self, id<<1|1);
};
build(build, 1);
}
answer(C, X, Y);
}
