#include "doll.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
typedef vector <ll> vecl;
using namespace std;
const int INF = 1e9;
int nam;
int c[1000005],g;
struct hap {int bit,wi,wh;};
vector <hap> sw;
int n,m,k;
int edge[1000005][2];
bool cmp(hap x,hap y) {
return x.bit < y.bit;
}
void build(int x,int go,int bit) {
if(!nam) return;
c[x] = ++g;
if(x*2 >= k) {
edge[g][0] = edge[g][1] = -1;
sw.push_back({bit,g,0});
sw.push_back({bit+(1 << go),g,1});
nam--;
return;
}
build(x*2+1,go+1,bit+(1 << go)), build(x*2,go+1,bit);
edge[c[x]][0] = (c[x*2] == -1 ? -1 : -c[x*2]);
edge[c[x]][1] = (c[x*2+1] == -1 ? -1 :-c[x*2+1]);
}
void create_circuit(int M,vec A) {
memset(c,-1,sizeof(c));
n = A.size(), m = M;
for(k = 1;k <= n;k *= 2);
nam = n/2+1;
build(1,0,0);
sort(sw.begin(),sw.end(),cmp);
for(int i = 0;i < n;i++) edge[sw[i].wi][sw[i].wh] = A[i];
edge[sw.back().wi][sw.back().wh] = 0;
vec le,ri;
for(int i = 1;i <= g;i++) {
le.push_back(edge[i][0]);
ri.push_back(edge[i][1]);
}
answer(vector<int>(m+1,-1),le,ri);
}
