PROGRAM INF93(INPUT,OUTPUT);                                
 TYPE PTR=^KNOTEN;                                          
     KNOTEN=RECORD                                          
             INFO:INTEGER;                                  
             RECHTS,LINKS:PTR                               
            END;                                            
 VAR W:PTR;(*×URZEL DES ÂAUMES*)                            
     P:PTR;X:INTEGER;B:CHAR;                                
                                                            
 FUNCTION SUCHEN(X:INTEGER):PTR;                            
 (*LIEFERE ÚEIGER AUF ÅLEMENT MIT ÉNFO X. ÓONST NIL       *)
 VAR Z:PTR;FOUND:BOOLEAN;                                   
 BEGIN                                                      
  FOUND:=FALSE;Z:=W;                                        
  WHILE NOT FOUND AND(Z<>NIL) DO (*ITERATIV*)               
   BEGIN                                                    
    IF X=Z^.INFO THEN FOUND:=TRUE ELSE                      
    IF X>Z^.INFO THEN Z:=Z^.RECHTS                          
                 ELSE Z:=Z^.LINKS                           
   END;                                                     
  SUCHEN:=Z                                                 
 END;(*SUCHEN*)                                             
                                                            
 PROCEDURE EINFUEGEN(X:INTEGER;VAR W:PTR);                  
 (*ÆUEGE X IN ÂAUM W EIN, FALLS DIESER NOCH KEIN ÅLEMENT  *)
 (*MIT EINER SOLCHEN ÉNFORATION ENTHAELT.(REKURSIV)       *)
 BEGIN                                                      
  IF W=NIL THEN (*ÂAUM IST LEER, NEUER ÅINTRAG*)            
   BEGIN NEW(W); W^.INFO:=X; W^.LINKS:=NIL; W^.RECHTS:=NIL  
   END                                                      
  ELSE                                                      
   IF X<W^.INFO THEN EINFUEGEN(X,W^.LINKS ) ELSE            
   IF X>W^.INFO THEN EINFUEGEN(X,W^.RECHTS)                 
 END;(*EINFUEGEN*)                                          
                                                            
 PROCEDURE LOESCHEN(X:INTEGER;VAR W:PTR);                   
 (*ÌOESCHE IM ÂAUM W*)                                      
                                                            
  PROCEDURE ERSETZE(VAR Z:PTR);                             
  (*ÅRSETZE W^ DURCH DAS GROESSTE ÅLEMENT DES ÂAUMES Z*)    
  BEGIN                                                     
   IF Z^.RECHTS<>NIL THEN ERSETZE(Z^.RECHTS) ELSE           
    BEGIN                                                   
     W^.INFO:=Z^.INFO;  (*ERSETZE ÉNHALT UND AKTUALISIERE *)
     Z:=Z^.LINKS        (*DEN ÚEIGER DES ÖORGAENGERS      *)
    END                                                     
  END;(*ERSETZE*)                                           
                                                            
 BEGIN                                                      
  IF W=NIL THEN WRITELN(X," NICHT IM ÂAUM") ELSE            
  IF X<W^.INFO THEN LOESCHEN(X,W^.LINKS )  ELSE             
  IF X>W^.INFO THEN LOESCHEN(X,W^.RECHTS)  ELSE             
   BEGIN                                                    
    IF W^.LINKS =NIL THEN W:=W^.RECHTS (*HOCHSCHIEBEN*) ELSE
    IF W^.RECHTS=NIL THEN W:=W^.LINKS  (*HOCHSCHIEBEN*) ELSE
     ERSETZE(W^.LINKS)                                      
   END                                                      
 END;(*LOESCHEN*)                                           
                                                            
BEGIN                                                       
 READ(B);W:=NIL;                                            
 WHILE B<>"_" DO                                            
  BEGIN READLN(X);                                          
   CASE B OF                                                
    "?":BEGIN P:=SUCHEN(X);                                 
         IF P=NIL THEN WRITE("NICHT ")                      
         WRITELN("GEFUNDEN")                                
        END;                                                
    "+":EINFUEGEN(X,W);                                     
    "-":LOESCHEN(X,W)                                       
   END;                                                     
   READ(B)                                                  
  END                                                       
END.