mt19937 rnd(time(0));
void splay(int x){
	for(int y=t[x].fa;y;rotate(x),y=t[x].fa){
		if(t[y].fa) rotate(rnd()&1?y:x);
	}
	rt=x;
}