#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000009
struct Switch{
int cur = 0;
vector<int> ch = {-INF, -INF};
Switch(){}
};
struct Trigger{
int next = -INF;
Trigger(){}
};
void create_circuit(int m, vector<int> events) {
events.push_back(0);
int n = events.size();
vector<int> cnt(m+1, 0);
for(int i = 0; i<n; i++) cnt[events[i]]++;
vector<Trigger> triggers(m+1);
// cout << n << endl;
vector<Switch> switches(2*n);
// cout << 1 << endl;
vector<int> par(2*n);
// cout << 1 << endl;
int curSwitch = 1;
for(int i = 0; i<=m; i++){
if(cnt[i] == 1) continue;
if(cnt[i] == 0){
triggers[i].next = 0;
continue;
}
queue<int> q;
triggers[i].next = -curSwitch;
par[curSwitch] = i;
q.push(curSwitch++);
int curCnt = 2;
while(curCnt < cnt[i]){
int s = q.front();
q.pop();
switches[s].ch[0] = -(curSwitch++);
switches[s].ch[1] = -(curSwitch++);
curCnt += 2;
q.push(-switches[s].ch[0]);
q.push(-switches[s].ch[1]);
par[-switches[s].ch[0]] = -s;
par[-switches[s].ch[1]] = -s;
}
}
// cout << curSwitch << endl;
stack<int> st;
st.push(0);
int ind = 0;
while(ind < n){
int v = st.top();
st.pop();
// cout << v << endl;
if(v >= 0){
if(triggers[v].next == -INF) triggers[v].next = events[ind];
if(triggers[v].next == events[ind]) ind++;
st.push(triggers[v].next);
}
else{
v = -v;
if(switches[v].ch[switches[v].cur] == -INF) switches[v].ch[switches[v].cur] = events[ind];
if(switches[v].ch[switches[v].cur] == events[ind]){
ind++;
}
st.push(switches[v].ch[switches[v].cur]);
switches[v].cur = 1-switches[v].cur;
}
// cout << n-ind << endl;
}
for(int i = 1; i<curSwitch; i++){
if(switches[i].ch[1] == -INF){
int p = par[i];
int o = switches[-p].ch[0];
int num = switches[-o].ch[1];
switches[-o].ch[1] = p;
switches[i].ch[1] = num;
}
}
// cout << switches[1].ch[1] << endl;
vector<int> C, X, Y;
C.resize(m+1);
for(int i = 1; i<curSwitch; i++){
X.push_back(switches[i].ch[0]);
Y.push_back(switches[i].ch[1]);
}
for(int i = 0; i<=m; i++) C[i] = triggers[i].next;
answer(C, X, Y);
}
