#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
struct sw {
int nxt[2];
bool end = false;
int flag = 0;
int tl, tr;
};
int skip = 0;
vector<sw> switches;
int cnt = 1;
int t_cnt = 0;
void build(int v, int tl, int tr) {
if (tl == tr-1) {
switches[v].end = true;
t_cnt += 2;
if (tl <= skip) {
switches[v].nxt[0] = 1;
t_cnt--;
}
return;
}
// prune the tree from the left side
int tm = (tl+tr)/2;
if (tm <= skip) {
switches[v].nxt[0] = 1;
switches[v].nxt[1] = ++cnt;
switches[cnt].tl = tm+1;
switches[cnt].tr = tr;
}
else {
switches[v].nxt[0] = ++cnt;
switches[cnt].tl = tl;
switches[cnt].tr = tm;
switches[v].nxt[1] = ++cnt;
switches[cnt].tl = tm+1;
switches[cnt].tr = tr;
}
if (switches[v].nxt[0] != 1) build(switches[v].nxt[0], tl, tm);
if (switches[v].nxt[1] != 1) build(switches[v].nxt[1], tm+1, tr);
}
void walk(int v, int trig) {
if (switches[v].nxt[switches[v].flag] == 0) {
// link the trigger to this switch
switches[v].nxt[switches[v].flag] = trig;
switches[v].flag = 1-switches[v].flag;
t_cnt--;
return;
}
switches[v].flag = 1-switches[v].flag;
walk(switches[v].nxt[1-switches[v].flag], trig);
}
void create_circuit(int M, vector<int> A) {
int n = A.size()+1;
int k = 1;
while (k < n) k *= 2;
switches.resize(k+1);
skip = k-n;
switches[1].tl = 1, switches[1].tr = k;
build(1, 1, k);
for (int i = 0; i < n-1; i++) walk(1, M+A[i]);
while (t_cnt > 1) walk(1, 1);
vector<int> c(M+1, -1), x(cnt), y(cnt);
for (int i = 1; i <= cnt; i++) {
if (switches[i].end) {
if (switches[i].nxt[0] > M) x[i-1] = switches[i].nxt[0]-M;
else x[i-1] = -switches[i].nxt[0];
if (switches[i].nxt[1] > M) y[i-1] = switches[i].nxt[1]-M;
else y[i-1] = -switches[i].nxt[1];
}
else {
x[i-1] = -switches[i].nxt[0];
y[i-1] = -switches[i].nxt[1];
}
}
answer(c, x, y);
return;
}
