#include "doll.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <queue>
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;
vector<int> C, X, Y;
vector<pii> candidate;
int sz1 = 0;
inline void fill(int u, int sz, int num)
{
if (sz == 2)
{
candidate.push_back({num | (sz1 / sz), -(u + 1)});
candidate.push_back({num, u + 1});
}
else
{
X.push_back(0); Y.push_back(0);
X[u] = -X.size();
fill(X.size() - 1, sz / 2, num);
X.push_back(0); Y.push_back(0);
Y[u] = -X.size();
fill(X.size() - 1, sz / 2, num | (sz1 / sz));
}
}
inline void rs(int u, int sz, int esz, int num)
{
if (sz == 2)
{
candidate.push_back({num | (sz1 / sz), -u - 1});
if (esz & 1) {candidate.push_back({num, u + 1});}
else {X[u] = -1;}
}
else
{
X.push_back(0); Y.push_back(0);
Y[u] = -Y.size();
rs(Y.size() - 1, sz / 2, esz, num | (sz1 / sz));
if (esz & (sz / 2))
{
X.push_back(0); Y.push_back(0);
X[u] = -X.size();
fill(X.size() - 1, sz / 2, num);
}
else {X[u] = -1;}
}
}
void buildSwitch(int size)
{
if (size == 2)
{
sz1 = 2;
fill(0, 2, 0);
return;
}
sz1 = 1;
while (sz1 < size) {sz1 <<= 1;}
X.push_back(0); Y.push_back(0);
X[0] = -X.size();
X.push_back(0); Y.push_back(0);
Y[0] = -X.size();
rs(-X[0] - 1, sz1 / 2, (sz1 / 2) - 1, 0);
rs(-Y[0] - 1, sz1 / 2, size - (sz1 / 2) - 1, 1);
//cerr << "SIZE : " << u << " " << adj[u].size() << "\n";
}
void create_circuit(int M, vector<int> A)
{
C.assign(M + 1, 0);
A.push_back(0); X.push_back(0); Y.push_back(0);
for (int i = 0; i <= M; i++) {C[i] = -X.size();}
buildSwitch(A.size());
sort(candidate.begin(), candidate.end());
assert(candidate.size() == A.size());
for (int i = 0; i < candidate.size(); i++)
{
//cerr << "Candidate : " << candidate[i].fst << " " << candidate[i].snd << "\n";
if (candidate[i].snd < 0)
{
Y[-candidate[i].snd - 1] = A[i];
}
else
{
X[candidate[i].snd - 1] = A[i];
}
}
candidate.clear();
answer(C, X, Y);
}
