#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
int N;
int k;
const int rt = 1e9;
vector<int> I;
void create_circuit(int M, vector<int> A)
{
N = A.size();
if(A.size() == 1)
{
vector<int> C(M+1, 0);
C[0] = A[0];
vector<int> X(0), Y(0);
answer(C, X, Y);
return;
}
// assert(A.size() > 1);
for(k = 0; (1 << k) < N; k++); //2^k >= N
I = vector<int>( (1 << k) );
for(int i = 0; i < (1 << k); i++)
I[i] = i;
sort(I.begin(), I.end(), [] (int p, int q)
{
for(int y = 0; y < k; y++)
{
if((p & (1 << y)) < (q & (1 << y)))
return 1;
else if((q & (1 << y)) < (p & (1 << y)))
return 0;
}
return 0;
});
// for(int i:I) cerr << i << ' ';
// cerr << '\n';
vector<int> J(N);
for(int i = 0; i < N; i++) J[i] = I.size() - N + i;
sort(J.begin(), J.end(), [] (int x, int y)
{
return I[x] < I[y];
});
vector<int> A1[k+1];
A1[k] = vector<int>((1 << k), rt);
for(int i = 1; i < N; i++)
A1[k][ J[i-1] ] = A[i];
A1[k][J[N-1]] = 0;
int S = 0;
vector<int> C(M+1);
vector<int> X;
vector<int> Y;
for(int l = k-1; l >= 0; l--)
{
for(int i = 0; i < (1 << l); i++)
{
if(A1[l+1][2*i] == A1[l+1][2*i+1])
A1[l].push_back(A1[l+1][2*i]);
else
{
S++;
A1[l].push_back(-S);
X.push_back(A1[l+1][2*i]);
Y.push_back(A1[l+1][2*i+1]);
}
}
}
C[0] = A[0];
for(int i = 1; i <= M; i++)
C[i] = -S;
for(int j = 1; j <= S; j++)
{
if(X[j-1] == rt)
X[j-1] = -S;
if(Y[j-1] == rt)
Y[j-1] = -S;
}
// for(int l = 0; l <= k; l++)
// {
// for(int i = 0; i < (1 << l); i++) cerr << A1[l][i] << ' ';
// cerr << '\n';
// }
// cerr << "S = " << S << '\n';
answer(C, X, Y);
}
