// 平衡树 splay 模板
void rotate( int i )
{
    int D = dad[i],G = dad[D],S = son[i][ !typ[i] ];
    son[G][ typ[D] ] = i,dad[S] = D;
    son[D][ typ[i] ] = S,dad[D] = i;
    son[i][ !typ[i] ] = D,dad[i] = G;
    typ[S] = typ[i],typ[i] = typ[D],typ[D] = !typ[S];
    update( D );
}

void splay( int i )
{
    while( typ[i] != 2 )
    {
        if( typ[ dad[i] ] != 2 )
            if( typ[i] == typ[ dad[i] ] ) rotate( dad[i] ); else rotate( i );
        rotate( i );
    }
    update( i );
}