#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
int mlevel;
int cnt = 1;
int pow2[25];
int bigN;
int sequence[200005];
vector<int> X, Y;
struct switcher{
switcher *left = nullptr, *right = nullptr;
int level, id, lnode, rnode, state = 0;
switcher(int n, int lv, int offset){
id = cnt;
cnt++;
if (lv == 0){
if (n == 2){
lnode = 1;
rnode = 1;
}
else{
lnode = 1;
rnode = -1;
}
}
else{
if (n > pow2[lv]){
left = new switcher(n-pow2[lv],lv-1,offset);
right = new switcher(pow2[lv],lv-1,offset+n-pow2[lv]);
lnode = -left->id;
rnode = -right->id;
}
else{
right = new switcher(n,lv-1,offset);
lnode = -1;
rnode = -right->id;
}
}
}
void revisit(switcher *r){
if (lnode == -1){
left = r;
}
if (rnode == -1){
right = r;
}
if (left != nullptr && left != r){
left->revisit(r);
}
if (right != r && right != nullptr){
right->revisit(r);
}
}
}*root;
void dfs(switcher *cur, int nx){
if (nx > bigN) return;
if (cur->state == 0){
cur->state = 1;
if (cur->left == nullptr){
cur->lnode = sequence[nx];
X[cur->id-1] = sequence[nx];
dfs(root,nx+1);
}
else{
X[cur->id-1] = -cur->left->id;
dfs(cur->left,nx);
}
}
else{
cur->state = 0;
if (cur->right == nullptr){
cur->lnode = sequence[nx];
Y[cur->id-1] = sequence[nx];
dfs(root,nx+1);
}
else{
Y[cur->id-1] = -cur->right->id;
dfs(cur->right,nx);
}
}
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
bigN = N;
vector<int> C;
C.resize(M+1);
if (N == 1){
C[0] = A[0];
C[1] = 0;
answer(C,X,Y);
return;
}
pow2[0] = 1;
for (int i = 1; i < 25; ++i){
pow2[i] = pow2[i-1]*2;
}
C[0] = A[0];
for (int i = 1; i <= M; ++i){
C[i] = -1;
}
for (int i = 0; i < A.size(); ++i){
if (i == A.size()-1){
sequence[i+1] = 0;
}
else sequence[i+1] = A[i+1];
}
//cout << "YEET\n" << flush;
int x = 1, p = 0;
while (x < N){
p++;
x *= 2;
}
root = new switcher(N,p-1,1);
//cout << "YEET\n" << flush;
X.resize(cnt);
Y.resize(cnt);
//cout << "YEET\n" << flush;
root->revisit(root);
//cout << "YEET\n" << flush;
switcher *a = root;
//cout << "YEET\n" << flush;
dfs(a,1);
//cout << "YEET\n" << flush;
answer(C, X, Y);
}
