#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> X, Y, C;
struct trigger {
int id;
int type;
trigger() {}
trigger(int typ) {
if (typ != 0) {
id = typ;
type = 1;
} else {
X.push_back(0);
Y.push_back(0);
id = X.size();
type = 0;
}
}
void connect_parent(int par) {
C[par] = -id;
}
void connect_X(trigger x) {
if (x.type == 0)
X[id - 1] = -x.id;
else
X[id - 1] = x.id;
}
void connect_Y(trigger y) {
if (y.type == 0)
Y[id - 1] = -y.id;
else
Y[id - 1] = y.id;
}
};
void set_idxs(int curr, int idx, int depth, int max_node, trigger node, vector<trigger> &targets) {
if (curr * 2 >= max_node) {
int xi = idx, yi = idx + (1 << depth);
node.connect_X(trigger(targets[xi]));
node.connect_Y(trigger(targets[yi]));
return;
}
trigger xnode(0);
trigger ynode(0);
set_idxs(curr*2, idx, depth + 1, max_node, xnode, targets);
set_idxs(curr*2+1, idx + (1 << depth), depth + 1, max_node, ynode, targets);
node.connect_X(xnode);
node.connect_Y(ynode);
}
void create_device(int node, trigger root, vector<trigger> targets) {
int siz = 2, needed = 2;
while (siz < targets.size())
siz *= 2, needed += siz;
while (targets.size() < siz)
{
targets.push_back(root);
swap(targets[targets.size() - 1], targets[targets.size() - 2]);
}
set_idxs(1, 0, 0, siz, root, targets);
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
C.resize(M+1);
vector<trigger> targets;
for (int i : A)
targets.push_back(trigger(i));
trigger zer;
zer.type = 1, zer.id = 0;
targets.push_back(zer);
C[0] = -1;
trigger rootdevice(0);
for (int i = 1; i <= M; i++)
C[i] = -rootdevice.id;
create_device(0, rootdevice, targets);
answer(C, X, Y);
}
