#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int counter = 0;
struct Node {
array<Node*, 2> c = {nullptr, nullptr};
int to = 0, idx = -1;
bool terminal() {
return c[0] == nullptr && c[1] == nullptr;
}
};
Node* construct(int sz, int depth) {
if(sz <= 0) return nullptr;
Node* root = new Node();
if(depth <= 0) return root;
root->idx = ++counter;
int sz_l = 1<<(31-__builtin_clz(sz));
if((1 << (depth-1)) >= sz) {
root->c[0] = nullptr;
root->c[1] = construct(sz, depth-1);
}
else {
if(sz_l == sz && sz > 1) sz_l /= 2;
int prev = counter;
root->c[0] = construct(sz-sz_l, depth-1);
int temp = counter-prev;
root->c[1] = construct(sz_l, depth-1);
}
return root;
}
// first time going to terminal node
void walk(Node* curr, Node* root, int target, vector<int> &X, vector<int> &Y) {
Node* to = curr->c[curr->to];
if(!to) {
if(curr->to) Y[curr->idx-1] = -root->idx;
else X[curr->idx-1] = -root->idx;
curr->to ^= 1;
walk(root, root, target, X, Y);
}
else if(to->terminal()) {
if(curr->to) Y[curr->idx-1] = target;
else X[curr->idx-1] = target;
curr->to ^= 1;
}
else {
if(curr->to) Y[curr->idx-1] = -to->idx;
else X[curr->idx-1] = -to->idx;
curr->to ^= 1;
walk(to, root, target, X, Y);
}
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
int depth = 31-__builtin_clz(N-1)+1;
Node* root = construct(N, depth);
vector<int> C(M+1);
vector<int> X(counter, -10000), Y(counter, -10000);
C[0] = A[0];
for(int i = 1; i <= M; i++) C[i] = -1;
for(int i = 1; i < N; i++) {
walk(root, root, A[i], X, Y);
}
walk(root, root, 0, X, Y);
answer(C, X, Y);
}
