#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
#define forR(i, n) for (int i = 0; i < (n); i++)
void answer(Vi C, Vi X, Vi Y);
Vi C, X, Y;
Vi swState;
int getLevelSW(int sz) {
int level = 1, maxSz = 2;
while (sz > maxSz) {
level++, maxSz *= 2;
}
return level;
}
int getSW() {
int swNo = -1 - X.size();
X.push_back(0); Y.push_back(0); swState.push_back(0);
return swNo;
}
void setSWX(int sw, int t) {
X[-1 - sw] = t;
}
void setSWY(int sw, int t) {
Y[-1 - sw] = t;
}
int getStateSW(int sw) {
int state = swState[sw];
swState[sw] = 1 - state;
return state;
}
int& goAlong(int node) {
int* nodePtr = NULL;
for (int i = 0; node < 0; i++) {
int sw = -1 - node;
if (getStateSW(sw) == 0) {
nodePtr = &X[sw];
} else {
nodePtr = &Y[sw];
}
node = *nodePtr;
}
return *nodePtr;
}
int buildLevelSW(int lvl, int nSkip = 0) {
int root = getSW();
Vi sws(1, root);
for (int i = 1; i < lvl; i++) {
Vi sw_lvl;
int lvl_skip = 1 << (lvl - i);
for (int sw : sws) {
if (nSkip >= lvl_skip) {
int sw1 = getSW();
sw_lvl.push_back(sw1);
setSWX(sw, root);
setSWY(sw, sw1);
nSkip -= lvl_skip;
} else {
int sw0 = getSW(), sw1 = getSW();
sw_lvl.push_back(sw0);
sw_lvl.push_back(sw1);
setSWX(sw, sw0);
setSWY(sw, sw1);
}
}
sws = sw_lvl;
}
if (nSkip > 0) {
setSWX(sws[0], root);
}
return root;
}
void build_answer(int node, const Vi& nexts) {
if (nexts.size() == 0) {
C[node] = 0;
return;
} else if (nexts.size() == 1) {
C[node] = nexts[0];
return;
}
int lvlSW = getLevelSW(nexts.size());
int root = buildLevelSW(lvlSW);
forR(i, ((1 << lvlSW) - nexts.size())) {
goAlong(root) = root;
}
for (int next : nexts) {
goAlong(root) = next;
}
C[node] = root;
}
void create_circuit(int M, Vi A) {
int n = A.size();
X = Y = swState = Vi();
C = Vi(M + 1);
C[0] = A[0];
Vii nexts(M + 1);
A.push_back(0);
forR(i, n) {
nexts[A[i]].push_back(A[i + 1]);
}
int lvl = getLevelSW(n);
int skips = (1 << lvl) - n;
int root = buildLevelSW(lvl, skips);
forR(i, n) {
goAlong(root) = A[i + 1];
}
forR(i, M) {
C[i + 1] = root;
}
//forR(i, M) {
// build_answer(i + 1, nexts[i + 1]);
//}
answer(C, X, Y);
}
