#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000009
struct Switch{
int cur = 0;
int ch[2] = {-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();
int cnt[m+1];
fill(cnt, cnt+m+1, 0);
for(int i = 0; i<n; i++) cnt[events[i]]++;
Trigger triggers[m+1];
// cout << n << endl;
Switch switches[2*n];
// cout << 1 << endl;
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;
}
}
stack<int> st;
st.push(0);
int ind = 0;
bool lol = false;
while(ind < n){
int v = st.top();
st.pop();
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]){
if(ind != n-1) ind++;
else{
if(lol){
ind++;
continue;
}
switches[v].ch[switches[v].cur] = -par[v];
lol = true;
}
}
st.push(switches[v].ch[switches[v].cur]);
switches[v].cur = 1-switches[v].cur;
}
}
// cout << switches[0].next << 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);
}
