#include <iostream>
#include <cstdio>
#include <queue>
using namespace std; const int maxn=1e5+;
struct Node{
int val,rev,max,min;
Node(){}
Node(int _rev,int _max,int _min){
this->rev=_rev;
this->max=_max;
this->min=_min;
}
};
Node node[maxn];
int son[maxn][];//0 表示左儿子，1表示右儿子
int father[maxn];
bool Root[maxn];
int ROOT;
int tot;
int n,q,op;
struct bnode{
int v,dep;
bnode(int _v,int _dep){
this->v=_v;
this->dep=_dep;
}
};
vector<int> DEEP[maxn];
void init(){
tot=;
ROOT=-;
memset(Root,,sizeof(Root));
}
void BFS(){
int i;
for(i=;i<maxn;++i){
DEEP[i].clear();
}
if(ROOT==-) return;
queue<bnode> que;
que.push(bnode(ROOT,));
while(!que.empty()){
bnode t=que.front();
que.pop();
int v=t.v;
int dep=t.dep;
DEEP[dep].push_back(v);
if(son[v][]!=) que.push(bnode(son[v][],dep+));
if(son[v][]!=) que.push(bnode(son[v][],dep+));
}
}
void print(){
BFS();
int cnt=;
for(int j=;j<;++j){
if(DEEP[j].size()==) break;
cnt++;
printf("DEEP:%d==>",j);
for(int k=;k<DEEP[j].size();++k){
printf("%d ",DEEP[j][k]);
}
printf("\n");
}
if(!cnt) printf("The Tree is Empty\n");
}
void printVAL(){
int i;
for(i=;i<tot;++i){
printf("v%d val%d leftson%d rightson%d fa%d\n",i,node[i].val,son[i][],son[i][],father[i]);
}
}
void zig(int x){
int y=father[x];
int z=father[y];
son[y][]=son[x][];
if(son[x][]!=)
father[son[x][]]=y;
son[x][]=y;
if(y!=)
father[y]=x;
if(x!=)
father[x]=z;
if(z!=-&&z!=){
if(son[z][]==y){
son[z][]=x;
}
else {
son[z][]=x;
}
}
if(Root[y]){
Root[x]=true;
Root[y]=false;
ROOT=x;
}
}
void zag(int x){
int y=father[x];
int z=father[y];
son[y][]=son[x][];
if(son[x][])
father[son[x][]]=y;
son[x][]=y;
if(y)
father[y]=x;
if(x)
father[x]=z;
if(z!=-&&z!=){
if(son[z][]==y){
son[z][]=x;
}
else{
son[z][]=x;
}
}
if(Root[y]){
Root[x]=true;
Root[y]=false;
ROOT=x;
}
}
void zigzig(int x){
int y=father[x];
zig(y);
zig(x);
}
void zagzag(int x){
int y=father[x];
zag(y);
zag(x);
}
void zigzag(int x){
zig(x);zag(x);
}
void zagzig(int x){
zag(x);zig(x);
}
void Splay(int x){
while(!Root[x]){
int y=father[x];
int z=father[y];
if(z!=-&&!Root[z]){
if(son[z][]==y){
if(son[y][]==x){
zigzig(x);
}
else{
zag(x);zig(x);
}
}
if(son[z][]==y){
if(son[y][]==x){
zagzag(x);
}
else{
zig(x);zag(x);
}
}
}
else if(!Root[y]){
if(son[y][]==x){
zig(x);
}
else{
zag(x);
}
}
else {
if(son[y][]==x){
zig(x);
}
else {
zag(x);
}
}
// printf("==========\n");
// print();
// printVAL();
}
} int insert(int rt,int x){
if(rt==-){
rt=tot;
node[rt].val=x;
father[rt]=-;
Root[rt]=true;
ROOT=rt;
++tot;
return tot-;
}
if(x>node[rt].val){
if(son[rt][]==){
node[tot].val=x;
father[tot]=rt;
son[rt][]=tot;
tot++;
return tot-;
}
else insert(son[rt][],x);
}
else if(x<node[rt].val){
if(son[rt][]==){
node[tot].val=x;
father[tot]=rt;
son[rt][]=tot;
tot++;
return tot-;
}
else insert(son[rt][],x);
}
} int Search(int rt,int x){
// printf("rt%d x%d\n",rt,x);
if(rt==-){
//Exception
}
if(x==node[rt].val){
Splay(rt);
return rt;
}
if(x>node[rt].val){
if(son[rt][]==) return -;
return Search(son[rt][],x);
}
else if(x<node[rt].val){
if(son[rt][]==) return -;
return Search(son[rt][],x);
}
}
int SearchMax(int rt){
if(son[rt][]!=){
int x=son[rt][];
if(son[x][]==) return x;
return SearchMax(son[x][]);
}
return rt;
}
bool Delete(int x){
int id=Search(ROOT,x);
if(id==-) return false;
Splay(id);
// print();
// printf("=======\n");
int left=son[id][];
int right=son[id][];
son[id][]=;
son[id][]=;
if(left)
father[left]=-;
if(right)
father[right]=-;
Root[id]=false;
if(left)
Root[left]=true;
if(left)
ROOT=left;
if(left){
int lmx=SearchMax(left);
// printf("left%d lmx%d\n",left,lmx);
// print();
Splay(lmx);
son[lmx][]=right;
father[right]=lmx;
father[lmx]=-;
Root[id]=false;
Root[lmx]=true;
ROOT=lmx;
}
else if(right){
father[right]=-;
Root[id]=false;
Root[right]=true;
ROOT=right;
}
else{
init();
}
return true;
// print();
}
int findRoot(){ } void INSERT(int rt,int x){
int id=insert(rt,x);
printf("After insert\n");
print();
Splay(id);
printf("After Splay\n");
print();
}
int main(){
init();
scanf("%d%d",&n,&q);
//少写一个%d
int i,x;
for(i=;i<n;++i){
scanf("%d",&x);
INSERT(ROOT,x);
}
// printVAL();
for(i=;i<q;++i){
scanf("%d",&op);
if(op==){
scanf("%d",&x);
INSERT(ROOT,x);
}
else if(op==){
scanf("%d",&x);
int r=Delete(x);
if(r){
printf("Delete %d successful\n",x);
}
else printf("NOT FIND %d\n",x);
}
else if(op==){
scanf("%d",&x);
int id;
// print();
if((id=Search(ROOT,x))!=-){
printf("%d FIND v is %d\n",x,id);
}
else{
printf("%d NOT FIND\n",x);
}
}
else if(op==){
// printf("there22\n");
// printVAL();
print();
}
}
return ;
}