#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vll vector<int>
#define ll int
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
vector<int> XP,YP;
const int NM=1e6+10;
ll cp[NM],final[NM],label=0,father_of_all=-1;
vll fast_order(ll n)
{
if(n==2)
return {1,2};
vll ans;
ll hn=n/2;
for(int i=1;i<=n;i+=2)
ans.pb(i);
vll hans(hn);
vll np=fast_order(n/2);
for(int j=0;j<hn;j++)
hans[np[j]-1]=ans[j];
ans.clear();
for(auto i:hans)
ans.pb(i);
for(auto i:hans)
ans.pb(i+1);
return ans;
}
vll childx,childy,order_,npp;
int label_it(vll&p,int l,int r,bool lp=0)
{
// cout<<"Range "<<l<<' '<<r<<' '<<" p: ";
// for(int i=l;i<=r;i++)
// {
// cout<<p[i]<<' ';
// }
// cout<<endl;
if((l-r)==0){
// cout<<"Assigned ";
if(p[l]==-NM)
{
// cout<<father_of_all<<endl;
return father_of_all;
}
// cout<<p[l]<<endl;
return p[l];
}
int mid=(l+r)/2;
bool use=0;
for(int i=l;i<=r;i++)
{
if(p[i]!=-NM)
{
use=1;
break;
}
}
label++;
int usep=-label;
int fk=-1;
if(!use)
{
// all minus one is subtree
// cout<<"Range "<<l<<' '<<r<<endl;
// cout<<"Child: "<<father_of_all<<' '<<father_of_all<<endl;
fk=childx.size();
childx.pb(father_of_all);
childy.pb(father_of_all);
}
else
{
int lc=label_it(p,l,mid,1);
int rc=label_it(p,mid+1,r,1);
fk=childx.size();
childx.pb(lc);
childy.pb(rc);
// cout<<"Range "<<l<<' '<<r<<endl;
// cout<<"Child: "<<XP.back()<<' '<<YP.back()<<endl;
}
// cout<<"Assigned to range "<<l<<' '<<r<<' ';
// cout<<usep<<endl;
order_.pb(fk);
npp.pb(usep);
return usep;
}
void muskil(int m,vector<int> a)
{
XP.clear();
YP.clear();
label=0;
vector<int> ans(m+1);
vector<int> child[m+2];
vector<int> cur;
cur.pb(0);
for(int j=0;j<a.size();j++)
cur.pb(a[j]);
cur.pb(0);
for(int j=1;j<cur.size();j++)
child[cur[j-1]].push_back(cur[j]);
int lps=0;
for(int i=0;i<=m;i++)
{
if(child[i].size()==0)continue;
if(child[i].size()==1)
{
ans[i]=child[i][0];
}
else
{
ll pw=1;
while(child[i].size()>pw)
pw*=2;
int zxp=child[i].size(),cpp=0;
vll order=fast_order(pw);
vll fl(pw,1);
// cout<<"before\n";
for(int j=zxp;j<pw;j++)
fl[j-zxp]=-NM;
for(int j=0;j<pw;)
{
order[j]--;
while(fl[order[j]]==-NM)
j++;
fl[order[j]]=child[i][cpp];
j++;
cpp++;
}
// cout<<"After\n";
// for(int j=0;j<pw;j++)
// {
// cout<<fl[j]<<' ';
// }
// cout<<endl;
ll og=label;
father_of_all=-label-1;
childx.clear();
childy.clear();
order_.clear();
npp.clear();
label_it(fl,0,pw-1);
ll last=XP.size();
for(int i=0;i<order_.size();i++)
{
XP.pb(0);
YP.pb(0);
}
for(int i=0;i<order_.size();i++)
{
ll cur=-og-npp[i]-1;
XP[last+cur]=(childx[i]);
YP[last+cur]=(childy[i]);
}
ans[i]=father_of_all;
}
}
answer(ans,XP,YP);
}
void create_circuit(int m, std::vector<int> a)
{
if(m==1)
{
muskil(m,a);
return;
}
XP.clear();
YP.clear();
label=0;
vector<int> ans(m+1);
vector<int> child[m+2];
vector<int> cur;
if(a.size()==16)
{
int v=a[0];
child[0].push_back(v);
for(int j=1;j<a.size();j++)
child[v].push_back(a[j]);
child[v].push_back(0);
int lps=0;
for(int j=0;j<=m;j++)
ans[j]=-1;
// cout<<"SZ: "<<child[v].size()<<endl;
for(auto i:{0,v})
{
if(child[i].size()==0)continue;
if(child[i].size()==1)
{
ans[i]=child[i][0];
}
else
{
ll pw=1;
while(child[i].size()>pw)
pw*=2;
int zxp=child[i].size(),cpp=0;
for(int j=zxp;j<pw;j++)
{
cp[cpp]=-NM;
cpp++;
}
for(int j=0;j<child[i].size();j++)
{
cp[cpp]=child[i][j];
cpp++;
}
vll order=fast_order(pw);
vll fl(pw);
for(int j=0;j<pw;j++)
{
order[j]--;
fl[order[j]]=cp[j];
final[order[j]]=cp[j];
}
// cout<<"final: ";
// for(int j=0;j<pw;j++)
// cout<<final[j]<<' ';
// cout<<endl;
// what switches?
ll og=label;
father_of_all=-label-1;
// pw then
// cout<<"Father "<<father_of_all<<endl;
// cout<<"Do label\n";
childx.clear();
childy.clear();
order_.clear();
npp.clear();
label_it(fl,0,pw-1);
// cout<<"Order: ";
// for(auto i:order_)
// cout<<i<<' ';
// cout<<endl;
// cout<<"npp: ";
// for(auto i:npp)
// cout<<i<<' ';
// cout<<endl;
ll last=XP.size();
for(int i=0;i<order_.size();i++)
{
XP.pb(0);
YP.pb(0);
}
for(int i=0;i<order_.size();i++)
{
ll cur=-og-npp[i]-1;
XP[last+cur]=(childx[i]);
YP[last+cur]=(childy[i]);
}
ans[i]=father_of_all;
}
/*
else if(child[i].size()==2) // solve atmost 2
{
// We need
s++;
ans[i]=-s;
x.pb(child[i][0]);
y.pb(child[i][1]);
}
else if(child[i].size()==3)
{
int s1=s+1;
int s2=s+2;
int s3=s+3;
s+=3;
ans[i]=-s1;
// s1
x.pb(-s2);
y.pb(-s3);
//s2
x.pb(-s1);
y.pb(child[i][1]);
//s3
x.pb(child[i][0]);
y.pb(child[i][2]);
}
else if(child[i].size()==4)
{
int s1=s+1;
int s2=s+2;
int s3=s+3;
s+=3;
ans[i]=-s1;
// s1
x.pb(-s2);
y.pb(-s3);
//s2
x.pb(child[i][0]);
y.pb(child[i][2]);
//s3
x.pb(child[i][1]);
y.pb(child[i][3]);
}
*/
}
// ans[cur.back()]=0;
// cout<<"Ans: ";
// for(int i=0;i<=m;i++)cout<<ans[i]<<' ';
// cout<<endl;
// for(int j=0;j<label;j++)
// {
// cout<<"Child of "<<-j-1<<' '<<XP[j]<<' '<<YP[j]<<endl;
// }
answer(ans,XP,YP);
}
else
{
cur.pb(0);
for(int j=0;j<a.size();j++)
cur.pb(a[j]);
cur.pb(0);
for(int j=1;j<cur.size();j++)
child[cur[j-1]].push_back(cur[j]);
int lps=0;
for(int i=0;i<=m;i++)
{
if(child[i].size()==0)continue;
if(child[i].size()==1)
{
ans[i]=child[i][0];
}
else
{
ll pw=1;
while(child[i].size()>pw)
pw*=2;
int zxp=child[i].size(),cpp=0;
for(int j=zxp;j<pw;j++)
{
cp[cpp]=-NM;
cpp++;
}
for(int j=0;j<child[i].size();j++)
{
cp[cpp]=child[i][j];
cpp++;
}
vll order=fast_order(pw);
vll fl(pw);
for(int j=0;j<pw;j++)
{
order[j]--;
fl[order[j]]=cp[j];
final[order[j]]=cp[j];
}
// cout<<"final: ";
// for(int j=0;j<pw;j++)
// cout<<final[j]<<' ';
// cout<<endl;
// what switches?
ll og=label;
father_of_all=-label-1;
// pw then
// cout<<"Father "<<father_of_all<<endl;
// cout<<"Do label\n";
childx.clear();
childy.clear();
order_.clear();
npp.clear();
label_it(fl,0,pw-1);
// cout<<"X: ";
// for(auto i:childx)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// cout<<"Y: ";
// for(auto i:childy)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// cout<<"Order: ";
// for(auto i:order_)
// cout<<i<<' ';
// cout<<endl;
// cout<<"npp: ";
// for(auto i:npp)
// cout<<i<<' ';
// cout<<endl;
ll last=XP.size();
for(int i=0;i<order_.size();i++)
{
XP.pb(0);
YP.pb(0);
}
for(int i=0;i<order_.size();i++)
{
ll cur=-og-npp[i]-1;
XP[last+cur]=(childx[i]);
YP[last+cur]=(childy[i]);
}
ans[i]=father_of_all;
}
/*
else if(child[i].size()==2) // solve atmost 2
{
// We need
s++;
ans[i]=-s;
x.pb(child[i][0]);
y.pb(child[i][1]);
}
else if(child[i].size()==3)
{
int s1=s+1;
int s2=s+2;
int s3=s+3;
s+=3;
ans[i]=-s1;
// s1
x.pb(-s2);
y.pb(-s3);
//s2
x.pb(-s1);
y.pb(child[i][1]);
//s3
x.pb(child[i][0]);
y.pb(child[i][2]);
}
else if(child[i].size()==4)
{
int s1=s+1;
int s2=s+2;
int s3=s+3;
s+=3;
ans[i]=-s1;
// s1
x.pb(-s2);
y.pb(-s3);
//s2
x.pb(child[i][0]);
y.pb(child[i][2]);
//s3
x.pb(child[i][1]);
y.pb(child[i][3]);
}
*/
}
// cout<<"ans\n";
// for(int i=0;i<=m;i++)
// {
// cout<<ans[i]<<' ';
// }
// cout<<endl;
// cout<<"xy\n";
// cout<<XP.size()<<endl;
// cout<<YP.size()<<endl;
// for(auto i:XP)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// for(auto i:YP)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// for(int i=0;i<label;i++)
// {
// cout<<XP[i]<<' '<<YP[i]<<endl;
// }
answer(ans,XP,YP);
}
}
