#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 200005;
int n, m;
int z;
vector<int> ans;
vector<int> ansx;
vector<int> ansy;
bool stg0(int x)
{
while (x % 2 == 0)
x /= 2;
return x == 1;
}
vector<int> v[N];
int q;
int f;
int bil(int l, int r, int pos, int d)
{
if (r < q)
{
--z;
ansx.push_back(z);
ansy.push_back(f);
return z;
}
if (l == r)
{
return pos;
}
int m = (l + r) / 2;
int u = --z;
ansx.push_back(0);
ansy.push_back(0);
if (d == 0)
f = u;
int uu = bil(l, m, pos, d + 1);
ansx[-u - 1] = uu;
uu = bil(m + 1, r, pos + (1 << d), d + 1);
ansy[-u - 1] = uu;
return u;
}
void create_circuit(int M_, std::vector<int> A)
{
n = sz(A);
m = M_;
for (int i = 0; i < n; ++i)
{
if (i < n - 1)
v[A[i]].push_back(A[i + 1]);
else
v[A[i]].push_back(0);
}
while (!stg0(q + n))
++q;
bil(0, q + n - 1, 0, 0);
vector<pair<int, pair<int, int> > > vv;
for (int i = 0; i < sz(ansx); ++i)
{
if (ansx[i] >= 0)
vv.push_back(m_p(ansx[i], m_p(i, 0)));
if (ansy[i] >= 0)
vv.push_back(m_p(ansy[i], m_p(i, 1)));
}
sort(all(vv));
assert(sz(vv) == n);
for (int i = 0; i < n; ++i)
{
if (i < n - 1)
{
if (vv[i].se.se == 0)
ansx[vv[i].se.fi] = A[i + 1];
else
ansy[vv[i].se.fi] = A[i + 1];
}
else
{
if (vv[i].se.se == 0)
ansx[vv[i].se.fi] = 0;
else
ansy[vv[i].se.fi] = 0;
}
}
ans.push_back(A[0]);
for (int x = 1; x <= m; ++x)
{
ans.push_back(f);
}
answer(ans, ansx, ansy);
}
