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 break
                     else
          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 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^.info>c2^.info then c2^.dr:=c1^.st
                                                               else c2^.st:=c1^.st;
                                          c^.info:=c1^.info;
                                          dispose(c1);
                                          end
                   else begin
                        c1:=c^.dr;
                        c2:=c;
                        while c1^.st<>nil do begin
                                             c2:=c1;
                                             c1:=c1^.st;
                                             end;
                        if c1^.info>c2^.info then c2^.dr:=c1^.dr
                                             else c2^.st:=c1^.dr;
                        c^.info:=c1^.info;
                        dispose(c1);
                        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;
      writeln(ok);
      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.