//#include "doll.h"
#include <vector>
void create_circuit(int M, std::vector<int> A);
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int WRONG_ID = -16969420, ROOT_ID = WRONG_ID + 1;
vector<int> arr;
vector<int> x, y;
pair<int, int> buildTree(int l, int r) {
if(l == r) {
//cout << l << " " << r << " " << out(arr[l]) << endl;
return {arr[l], arr[l] != WRONG_ID};
}
int m = (l + r) / 2ll;
auto lftSon = buildTree(l, m);
auto rghtSon = buildTree(m + 1, r);
//cout << l << " " << r << " " << lftSon << " " << rghtSon << endl;
if(lftSon.second + rghtSon.second == 0) {
return {WRONG_ID, 0};
} else {
x.push_back(lftSon.first);
y.push_back(rghtSon.first);
return {-x.size(), lftSon.second + rghtSon.second};
}
}
int bitInverse(int ind, int pow2) {
int ret = 0;
for(int i = 0; i < pow2; i ++) {
if(ind & (1 << i)) {
ret |= (1 << (pow2 - 1 - i));
}
}
return ret;
}
void create_circuit(int M, std::vector<int> A) {
x.resize(0);
y.resize(0);
arr = A;
arr.push_back(WRONG_ID);
int pow2 = 0;
while((1 << pow2) < arr.size()) {
pow2 ++;
}
while(arr.size() < (1 << pow2)) {
arr.push_back(WRONG_ID);
}
arr[arr.size() - 1] = 0;
vector<pair<int, int> > prs;
for(int i = 0; i < arr.size(); i ++) {
int inv = bitInverse(i, pow2);
if(i < A.size()) {
prs.push_back({inv, -1});
//cout << out(prs.back()) << endl;
}
}
sort(prs.begin(), prs.end());
for(int i = 0; i < prs.size(); i ++) {
prs[i].second = arr[i];
}
for(int i = 0; i < prs.size(); i ++) {
arr[bitInverse(prs[i].first, pow2)] = prs[i].second;
}
pow2 = 1 << pow2;
int root = buildTree(0, pow2 - 1).first;
vector<int> ptr;
for(int i = 0; i <= M; i ++) {
ptr.push_back(root);
}
for(int i = 0; i < x.size(); i ++) {
if(x[i] == WRONG_ID) {
x[i] = root;
}
if(y[i] == WRONG_ID) {
y[i] = root;
}
}
x = {2, 1, -1, 8, 3, -4, -3, 9, -8, -13, -13, -9, -7};
y = {7, 4, -2, 6, 5, -5, -6, -13, -13, 0, -10, -11, -12};
answer(ptr, x, y);
return;
cout << "x = {";
for(int i = 0; i < x.size(); i ++) {
cout << x[i];
if(i != x.size() - 1) {
cout << ", ";
}
}
cout << "};" << endl;
cout << "y = {";
for(int i = 0; i < x.size(); i ++) {
cout << y[i];
if(i != y.size() - 1) {
cout << ", ";
}
}
cout << "};";
answer(ptr, x, y);
}
