PROGRAM INF73(INPUT,OUTPUT);                                                    
 CONST MAXN=12;                                                                 
 TYPE BMATRIX=ARRAY[1..MAXN,1..MAXN]OF BOOLEAN;                                 
VAR A,B,C:BMATRIX;                                                              
    D    :BMATRIX;                                          (*TABELLE ALLER   *)
                                                            (*DISJUNKTIONEN   *)
                                                            (*AUS ZEILEN DER  *)
                                                            (*TEILMATRIZEN    *)
    M,N,I,J,K,L1,L2,K2:INTEGER;                                                 
                                                                                
 PROCEDURE BESETZE(VAR A:BMATRIX);                                              
 VAR I,J,X:INTEGER;                                                             
                                                                                
 BEGIN                                                                          
  FOR I:=1 TO N DO                                                              
   FOR J:=1 TO N DO                                                             
    BEGIN                                                                       
     WRITE(I,J,"=>");                                                           
     READLN(X);A[I,J]:= X=0                                                     
    END;                                                                        
 END;                                                                           
                                                                                
 PROCEDURE DRUCKE(VAR A:BMATRIX);                                               
 VAR I,J,X:INTEGER;                                                             
                                                                                
 BEGIN                                                                          
  FOR I:=1 TO N DO                                                              
   BEGIN                                                                        
    FOR J:=1 TO N DO WRITE(ORD(A[I,J]));                                        
    WRITELN;                                                                    
   END;                                                                         
  WRITELN;                                                                      
 END;                                                                           
                                                                                
 PROCEDURE PROBE(VAR A,B,C:BMATRIX);                                            
 VAR I,J,K:INTEGER;B1:BOOLEAN;                                                  
                                                                                
 BEGIN                                                                          
  FOR I:=1 TO N DO                                                              
   FOR J:=1 TO N DO                                                             
    BEGIN B1:=FALSE;                                                            
     FOR K:=1 TO N DO                                                           
      B1:=B1 OR(A[I,K] AND B[K,J]);                                             
     IF B1<>C[I,J] THEN                                                         
      WRITELN("FEHLER:",ORD(C[I,J]),"STATT",ORD(B1),"BEI",I,J);                 
    END;                                                                        
  WRITELN("PROBE BEENDET");                                                     
 END;                                                                           
                                                                                
BEGIN                                                                           
 READLN(N);                                                                     
 BESETZE(A);                                                (*VORBELEGUNG DER *)
 BESETZE(B);                                                (*MATRIZEN        *)
                                                                                
 M:=1;K:=4;WHILE K<=N DO BEGIN K:=K*2;M:=M+1 END;           (*M = ÌLOG(N)º    *)
 L2:=0;                                                     (*L1 UND L2 BILDEN*)
 REPEAT                                                     (*GROESSTEN UND   *)
  L1:=L2+1;L2:=L1+M-1;IF L2>N THEN L2:=N;                   (*KLEINSTEN INDEX *)
                                                            (*IN TEILMATRIZEN *)
  FOR J:=1 TO N DO                                                              
   BEGIN D[1,J]:=FALSE;D[2,J]:=B[L2,J] END;                 (*ERZEUGE REKURSIV*)
                                                            (*IN D ALLE DISJ. *)
  K2:=1;                                                    (*DER TEILMATRIX B*)
  FOR K:=L2-1 DOWNTO L1 DO                                                      
   BEGIN K2:=2*K2;                                          (*K2=ANZAHL DER   *)
    FOR I:=1 TO K2 DO                                       (*DISJUNKTIONEN   *)
     FOR J:=1 TO N DO D[I+K2,J]:=D[I,J] OR B[K,J];          (*VERDOPPELE ANZ. *)
   END;                                                     (*DURCH DISJ. MIT *)
                                                            (*ZEILE K AUS B   *)
  FOR I:=1 TO N DO                                                              
   BEGIN                                                    (*UEBERTRAGE DIE  *)
    J:=0;FOR K:=L1 TO L2 DO J:=2*J+ORD(A[I,K]);J:=J+1;      (*DURCH A[I] INDI-*)
                                                            (*ZIERTE  ZEILE   *)
    IF L1=1 THEN(*C IST NOCH LEER*)                         (*D[J] NACH C[I]  *)
      FOR K:=1 TO N DO C[I,K]:=D[J,K]                       (*FALLS C BEREITS *)
    ELSE                                                    (*BESETZT, BILDE  *)
      FOR K:=1 TO N DO C[I,K]:=D[J,K]OR C[I,K]              (*DISJ. D[J]+C[I] *)
   END;                                                                         
                                                            (*BIS ALLE TEILM. *)
 UNTIL L2=N;                                                (*BEHANDELT WURDEN*)
                                                                                
 DRUCKE(A);DRUCKE(B);DRUCKE(C);                                                 
 PROBE(A,B,C);                                                                  
                                                                                
END.