void rotate(int x)

{

    int y=pre[x],z=pre[y],d=ch[y][]==x;

    ch[y][d^]=ch[x][d];pre[ch[x][d]]=y;

    ch[z][ch[z][]==y]=x;pre[x]=z;

    ch[x][d]=y;pre[y]=x;maintain(y);

}

int q[maxn],top;

void splay(int x)

{

    for(int i=x;i;i=pre[i]) q[++top]=i;

    if(q[top]!=x) fa[x]=fa[q[top]],fa[q[top]]=;

    while(top) pushdown(q[top--]);

    while(pre[x])

    {

        int y=pre[x],z=pre[y];

        if(pre[y]) if(ch[y][]==x^ch[z][]==y) rotate(x);else rotate(y);

        rotate(x);

    }

    maintain(x);

}