```

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string s;
struct node{
    int l,r;
    char c;
}h[N]; 
int cnt;
int idx;

void dfs1(){
    
    
    int u=cnt++;
    h[u].l=h[u].r=-1;
    h[u].c=s[idx];
    idx++;
    if(idx>=s.length())    return ;
    if(s[idx]!='#'){
        h[u].l=cnt;
        dfs1();
    }else    idx++;
    if(idx>=s.length())    return ;
    if(s[idx]!='#'){
        h[u].r=cnt;
        dfs1();
    }else idx++;
}

void build(){
    idx=0;
    cnt=0;
    dfs1()...