typedef int Int;struct BSTNode{	BSTNode *kid[2],pa;	Int val;	int cnt;}*root,*nil;nil=new BSTNode();root=nil;BSTNode * Search(BSTNode * node,Int val){	while(node!=nil && val!=node->val){		int drct=(val
     
      val)?0:1;		node=node->kid[drct];	}	return node;}BSTNode * Extrema(BSTNode * node,int drct){	while(node->kid[drct]!=nil)		node=node->kid[drct];	return node;}BSTNode * Cessor(BSTNode * node,int drct){	if(node->kid[drct]!=nil) return Extrema(node->kid[drct],1-drct);	BSTnode * p=node->pa;	while(p!=nil && p->kid[drct]==node){		node=p; p=p->pa;	}	return p;}void InitNode(BSTNode * node,Int val,int cnt=1){	if(node!=nil) delete node; node=new BSTNode();	node->val=val; node->cnt=cnt;	node->kid[0]=node->kid[1]=node->pa=nil;}void Insert(BSTNode * pos,Int val){	if(pos==nil)	{ Initnode(pos,val); return; }	BSTNode * node=new BSTNode();	InitNode(node,val,1);	BSTNode *p=pos;	while(p->val!=val){		int drct=(val
      
       val)?0:1;		if(p->kid[drct]==nil)		{ node->pa=p; p->kid[drct]=node; return;}		p=p->kid[drct];	}	p->cnt++;}bool Delete(Int val){	BSTNode *node=search(root,val);	if(node==nil) return false;	if(node->kid[0]==nil && node->kid[1]==0){		int drct=(node->pa->kid[0]==node)?0:1;		node->pa->kid[drct]=nil;		delete node; return true;	}	if(node->kid[0]==nil || node->kid[1]==0){		int padrt=(node->pa->kid[0]==node)?0:1;		int kidrt=(node->kid[1]==nil)?0:1;		node->pa->kid[padrt]=node->kid[kidrt];		node->kid[kidrt]->pa=node->pa;		delete node; return true;	}	BSTNode sucnode=Cessor(node,1);	int padrt=(node->pa->kid[0]==node)?0:1;	node->pa->kid[padrt]=sucnode;	sucnode->kid[0]=node->kid[0];	sucnode->kid[1]=node->kid[1];	delete node; return true;}