#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define sp << " " <<
vector<vector<int>> goes;
vector<int> X, Y;
void wire(int num, int l, int r, int ret = -1, int retto = 0, int repeattime = 1){
if (ret == -1){
int loog = __lg(r - l + 1);
cerr << l sp r sp loog << endl;
if (r - l + 1 == (1 << loog)){
repeattime = (1 << loog);
ret = 1;
}else{
repeattime = (1 << loog) * 2;
retto = -X.size();
ret = repeattime - r + l - 1;
}
}
int swc = X.size() - 1;
if (ret >= repeattime){
ret -= repeattime;
X[swc] = retto;
}else{
if (repeattime == 2){
X[swc] = goes[num][l];
}else{
X[swc] = -X.size() - 1;
X.push_back(0);
Y.push_back(0);
wire(num, l, r - repeattime / 2, ret, retto, repeattime / 2);
}
}
if (repeattime == 2){
Y[swc] = goes[num][r];
}else{
Y[swc] = -X.size() - 1;
X.push_back(0);
Y.push_back(0);
wire(num, r - repeattime / 2 + 1, r, 0, 0, repeattime / 2);
}
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
vector<int> Ret(M + 1);
goes.resize(M + 1);
goes[0].push_back(A[0]);
for (int i = 0; i < N; i++){
if (i == N - 1){
goes[A[i]].push_back(0);
}else{
goes[A[i]].push_back(A[i + 1]);
}
}
for (int i = 0; i <= M; i++){
if (goes[i].size() < 2){
if (goes[i].size())
Ret[i] = goes[i][0];
}else{
X.push_back(0);
Y.push_back(0);
Ret[i] = -X.size();
wire(i, 0, goes[i].size() - 1);
}
}
answer(Ret, X, Y);
}
