type pnr=^nr;
     nr=record
        info:longint;
        st,dr:pnr;
        end;
var p,nou,c,c1,c2:pnr;
    op,ok:byte;
    x,n,i:longint;

function verificare(p:pnr):boolean;
begin
if p=nil then verificare:=true
         else if((p^.st<>nil)and(p^.st^.info>p^.info))or((p^.dr<>nil)and(p^.dr^.info<p^.info))then verificare:=false
         else verificare:=verificare(p^.st) and verificare(p^.dr);
end;

procedure afisare(p:pnr);
begin
if p=nil then exit;
write(p^.info,' ');
afisare(p^.st);
afisare(p^.dr);
end;

begin
assign(input,'hashuri.in');
reset(input);
assign(output,'hashuri.out');
rewrite(output);
readln(n);
p:=nil;
for i:=1 to n do
  begin
  readln(op,x);
  case op of
    1:if p=nil then
        begin
        new(p);
        p^.info:=x;
        p^.st:=nil;
        p^.dr:=nil;
        end
               else
        begin
        c:=p;
        repeat
        if x<c^.info then if c^.st=nil then begin
                                            new(nou);
                                            c^.st:=nou;
                                            nou^.info:=x;
                                            nou^.st:=nil;
                                            nou^.dr:=nil;
                                            break;
                                            end
                                       else c:=c^.st
                     else if x=c^.info then break
                                       else
                       if c^.dr=nil then begin
                                         new(nou);
                                         c^.dr:=nou;
                                         nou^.info:=x;
                                         nou^.st:=nil;
                                         nou^.dr:=nil;
                                         break;
                                         end
                                     else c:=c^.dr;
        until false;
        end;
    2:begin
      c:=p;
      c1:=nil;
      while(c<>nil)and(c^.info<>x)do begin
                                     c1:=c;
                                     if x<c^.info then c:=c^.st
                                                  else c:=c^.dr;
                                     end;
      if c=nil then continue;
      if c^.dr=nil then if c^.st=nil then begin
                                          if c1<>nil then if x<c1^.info then c1^.st:=nil
                                                                        else c1^.dr:=nil
                                                     else p:=nil;
                                          dispose(c);
                                          end
                                     else begin
                                          c1:=c^.st;
                                          c2:=c;
                                          while c1^.dr<>nil do begin
                                                               c2:=c1;
                                                               c1:=c1^.dr;
                                                               end;
                                          if c1^.st=nil then begin
                                                             if c1^.info>c2^.info then c2^.dr:=nil
                                                                                  else c2^.st:=nil;
                                                             c^.info:=c1^.info;
                                                             dispose(c1);
                                                             end
                                                        else begin
                                                             if c1^.info>c2^.info then c2^.dr:=c1^.st
                                                                                  else c2^.st:=c1^.st;
                                                             c^.info:=c1^.info;
                                                             dispose(c1);
                                                             end;
                                          end
                   else begin
                        c1:=c^.dr;
                        c2:=c;
                        while c1^.st<>nil do begin
                                             c2:=c1;
                                             c1:=c1^.st;
                                             end;
                        if c1^.dr=nil then begin
                                           if c1^.info>c2^.info then c2^.dr:=nil
                                                                else c2^.st:=nil;
                                           c^.info:=c1^.info;
                                           dispose(c1);
                                           end
                                      else begin
                                           if c1^.info>c2^.info then c2^.dr:=c1^.dr
                                                                else c2^.st:=c1^.dr;
                                           c^.info:=c1^.info;
                                           dispose(c1);
                                           end;
                        end;
      end;
    3:begin
      c:=p;
      ok:=0;
      while(c<>nil)and(ok=0)do
        begin
        if x=c^.info then ok:=1
                     else if x<c^.info then c:=c^.st
                                       else c:=c^.dr;
        end;
      if ok=0 then writeln('0')
              else writeln('1');
      end;
    end;{
  if verificare(p)=false then begin
                              writeln('eroare la ',op,' ',x);
                              writeln('RSD:');
                              afisare(p);
                              break;
                              end;}
  end;
close(output);
close(input);
end.