#include<bits/stdc++.h>
using namespace std;
int fa[100005],son[100005][2],w[100005],sz[100005];
bool color[100005];
int root,tot;
void up(int p){sz[p]=sz[son[p][0]]+sz[son[p][1]];}
int id(int p){return w[p]>w[fa[p]];}
void rotate(int& y,int s){
    int x=son[y][!s],z=fa[y];
    son[y][!s]=son[x][s];
    fa[son[x][s]]=y;
    fa[x]=z;
    if(z)  son[z][id(y)]=x;
    else  root=x;
    son[x][s]=y;
    fa[y]=x;
    up(y);up(x);
}
void insertfixup(int i){
    int f;
    while((f=fa[i])&&(!color[f])){
        int g=fa[f],u=son[g][!id(f)];
        if(u&&!color[u]){
            color[u]=color[f]=1;
            color[g]=0;
            i=g;
            continue;
        }
        if(id(i)^id(f)){
            rotate(f,!id(i));
            swap(i,f);
        }
        color[f]=1;
        color[g]=0;
        rotate(g,!id(f));
    }
    color[root]=1;
}
void insert(int x){
    if(!root){
        w[root=++tot]=x;
        sz[root]=1;
        color[root]=1;
        return;
    }
    int now=root;
    for(;son[now][x>w[now]];now=son[now][x>w[now]])
        ++sz[now];
    ++sz[now];
    w[++tot]=x;
    fa[tot]=now;
    sz[tot]=1;
    son[now][x>w[now]]=tot;
    insertfixup(tot);
}
signed main(){
    freopen("1.txt","w",stdout);
    srand(time(0));
    for(int i=1;i<=10;i++){
        int x=rand();
        insert(x);
    }
    cout<<"root:"<<root<<'\n';
    for(int i=1;i<=10;i++){
        printf("%d:\nw:%d\nsub_size:%d\nfa:%d\nleft son&right son:%d %d\ncolor:",
        i,w[i],sz[i],fa[i],son[i][0],son[i][1]);
        cout<<color[i]<<"\n\n";
    }
}