#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1e6 + 10;
int s = 1, n, fake_vert;
vector<int> C, X, Y, A;
inline int create_switch(int x, int y) {
X.push_back(x);
Y.push_back(y);
s++;
return -(s - 1);
}
inline int create_trigger(int x) {
X.push_back(-s);
Y.push_back(x);
s++;
return -(s - 1);
}
int build(int l = 0, int r = n - 1) {
if (A[l] == fake_vert && A[r] == fake_vert) return fake_vert;
if (l == r) return A[l];
else {
int mid = (l + r) >> 1;
int a = build(l, mid);
int b = build(mid + 1, r);
//cerr << l << sep << r << sep << -s << sep << a << sep << b << endl;
return create_switch(a, b);
}
}
inline int f(int ind, int lg) {
int ans = 0;
while (lg--) {
ans = (ans << 1 | (ind & 1));
ind >>= 1;
}
return ans;
}
inline void print() {
debug("print")
for (int i = 0; i < int(C.size()); i++)
cerr << i << ": " << C[i] << endl;
cerr << endl;
cerr << endl;
for (int i = 0; i < int(X.size()); i++)
cerr << -(i + 1) << ": " << X[i] << sep << Y[i] << endl;
cerr << endl;
cerr << endl;
}
void create_circuit(int m, vector<int> A_) {
A = A_;
A.push_back(0);
A_.push_back(0);
C.resize(m + 1);
C[0] = A.front();
A.erase(A.begin());
A_.erase(A_.begin());
fake_vert = create_trigger(-1);
reverse(all(A));
while (__builtin_popcount(int(A.size())) > 1) A.push_back(fake_vert);
reverse(all(A));
n = A.size();
int lg = __builtin_ctz(n);
vector<pair<int, int>> tmp;
int ind = n - 1;
while (ind >= 0 && A[ind] >= 0) {
tmp.push_back({f(ind, lg), ind});
ind--;
}
sort(all(tmp));
for (int i = 0; i < int(A_.size()); i++)
A[tmp[i].second] = A_[i];
int root = build(0, n - 1);
Y[0] = root;
while (A.back() < 0) A.pop_back();
for (int i = 1; i <= m; i++) C[i] = root;
// assert(X.size() <= 2 * n);
// print();
answer(C, X, Y);
}
// TODO: change destincation of fake_vert to root
