#include "doll.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
namespace{
int n, m;
int cnt = 1;
vector<int> c, x, y;
vector<int> bot;
void build(int dep, int fin){
int id = cnt;
if(dep < fin){
cnt++;
x[id - 1] = -cnt;
build(dep + 1, fin);
cnt++;
y[id - 1] = -cnt;
build(dep + 1, fin);
}
else{
bot.push_back(cnt);
}
}
}
void create_circuit(int M, std::vector<int> A){
m = M;
n = A.size();
c.resize(m + 1);
x.resize(3 * n + 1);
y.resize(3 * n + 1);
fill(x.begin(), x.end(), 12345678);
fill(y.begin(), y.end(), 12345678);
A.push_back(0);
c[0] = A[0];
vector<vector<int>> nxt(m + 1);
for(int i = 0; i < n; i++){
nxt[A[i]].push_back(A[i + 1]);
}
for(int i = 1; i <= m; i++){
int sz = (int)nxt[i].size();
if(sz == 0) continue;
if(sz == 1){
c[i] = nxt[i][0];
continue;
}
int dep = 0;
while((1 << dep) < sz) dep++;
c[i] = -cnt;
int hi = cnt;
vector<int>().swap(bot);
build(1, dep);
vector<pair<int, int>> bott;
int cntt = 0;
for(auto &x: bot){
int now = 0, ori = cntt;
while(cntt > 0){
now *= 2;
now += cntt % 2;
cntt /= 2;
}
bott.emplace_back(x, now);
cntt = ori;
cntt++;
}
auto cmp = [&](pair<int, int> a, pair<int, int> b){
return a.second < b.second;
};
int szz = bot.size();
for(int j = 0; j < szz; j++) bot[j] = bott[j].first;
for(int j = 0; j < (1 << dep) - sz; j++){
if(j & 1) y[bot[j / 2] - 1] = -hi;
else x[bot[j / 2] - 1] = -hi;
}
for(int j = (1 << dep) - sz; j < (1 << dep); j++){
if(j & 1) y[bot[j / 2] - 1] = nxt[i][j - (1 << dep) - sz];
else x[bot[j / 2] - 1] = nxt[i][j - (1 << dep) - sz];
}
}
while(!x.empty() && x.back() == 12345678) x.pop_back();
while(!y.empty() && y.back() == 12345678) y.pop_back();
answer(c, x, y);
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp doll.cpp
