#include "doll.h"
#include<vector>
#include<algorithm>
#include<utility>
#include<array>
#include<map>
#include<set>
#include<cassert>
#include<iostream>
using namespace std;
#define V vector
#define rep(i,a,b) for(int i=a; i<(int)b; i++)
#define nl '\n'
#define _ << " " <<
#define dbg(x) cout << "?" << #x << " : " << x << endl;
const int N = 4e5+5;
const int B = 3;
int n, m;
V<int> a;
V<int> c, lc, rc;
int make(){
lc.push_back(-1);
rc.push_back(-1);
return -(int)lc.size();
}
int f(int x){
return -x-1;
}
V<int> leaves;
bool stat[N];
void create_circuit(int _m,V<int> _a){
a.swap(_a); a.push_back(0);
n = a.size(); m = _m;
// build tree
V<int> v(n,0);
while(v.size() > 1){
V<int> nxt;
if(v.size()%2==1){
int x=1, y=v[0];
int z = make();
lc[f(z)] = x; rc[f(z)] = y;
nxt.push_back(z);
}
for(int i=v.size()%2; i<(int)v.size(); i+=2){
int x=v[i], y=v[i+1];
int z = make();
lc[f(z)] = x; rc[f(z)] = y;
nxt.push_back(z);
}
v.swap(nxt);
}
for(int x=-1; ; x--){
int idx = -x-1;
if(lc[idx]==1) lc[idx] = -lc.size();
if(rc[idx]==1) rc[idx] = -rc.size();
// cout << x _ lc[idx] _ rc[idx] << nl;
if(x==-(int)lc.size()) break;
}
c = V<int>(m+1, -lc.size());
// return;
// simulate to find order of leaves
// dbg("LEAVES");
int x = -lc.size();
while((int)leaves.size() < n){
// dbg(x);
int idx = -x-1, y;
if(stat[idx]==0) y = lc[idx];
else y = rc[idx];
stat[idx] ^= 1;
if(y==0){
// cout << "LEAF" << nl;
// dbg(x);
leaves.push_back(x);
x = -lc.size();
}
else{
x = y;
}
}
rep(i,0,N) stat[i] = 0;
rep(i,0,n){
x = leaves[i];
int idx = -x-1;
if(lc[idx]==0){
lc[idx] = a[i];
}
else{
rc[idx] = a[i];
}
}
answer(c,lc,rc);
}
