// Please read "readme.txt" first.

#include<stdio.h>
#include<math.h>
#include <stdlib.h> 
#include <iostream>
#include <algorithm>
using namespace std;

int SizeOfMatrix,NumberOfRandomMutations,NumberOfRandomMutationsN,NumberOfAnswer,NumberOfMatrix,Matrix[40][40],
    List[100000][9][9],Length_of_List, M3[40][40];
double e[40];
FILE* f, * file, * fl, * fnew; 
char NameOfInput[100],NameOfOutput[100];

void change(int *aaa, int *bbb){
 int ccc=*aaa;
 *aaa=*bbb;
 *bbb=ccc;
}



void change_(int *pp, int *qq){
 for(int ii=0;ii<=SizeOfMatrix+1;ii++)
  change(&M3[ii][*pp],&M3[ii][*qq]);
 for(int ii=0;ii<=SizeOfMatrix+1;ii++)
  change(&M3[*pp][ii],&M3[*qq][ii]);
}

void copy_matrix(int M[40][40],int M1[40][40], int dim){
 for(int i=1;i<=dim;i++)
  for(int j=1;j<=dim;j++)
   M1[i][j]=M[i][j];
}
 
void read_matrix(){
 fscanf(file,"%d ",&SizeOfMatrix);
 for(int i=1;i<=SizeOfMatrix;i++)
  for(int j=1;j<=SizeOfMatrix;j++)
   fscanf(file,"%d ",&Matrix[i][j]);
 for(int i=1;i<=SizeOfMatrix;i++) 
  fscanf(file,"%lf ",&e[i]);  
}

void print_matrix(){
 f=fopen(NameOfOutput,"a");
 fprintf(f,"\n \n SizeOfMatrix=%d \n NumberOfMatrix=%d \n Matrix= " ,
                     SizeOfMatrix,NumberOfMatrix);
 for(int i=1;i<=SizeOfMatrix;i++){
  fprintf(f," \n       ");
  for(int j=1;j<=SizeOfMatrix;j++)
    if(Matrix[i][j]>=0) fprintf(f,"  %d",Matrix[i][j]);
    else fprintf(f," %d",Matrix[i][j]);
 }  
 fprintf(f,"\n"); 
 for(int i=1;i<=SizeOfMatrix;i++)
 fprintf(f,"  %lf",e[i]);
 fclose(f);
}

void print_last_line_column(int M1[40][40]){
 fnew=fopen("input_next.txt","a");
 fprintf(fnew,"\n %d \n ",SizeOfMatrix+1);
 for(int i=1;i<=SizeOfMatrix+1;i++){
  fprintf(fnew,"\n");
  for(int j=1;j<=SizeOfMatrix+1;j++)
   if(M1[i][j]>=0) fprintf(fnew," %d ",M1[i][j]);
   else fprintf(fnew,"%d ",M1[i][j]); 
 } 
 fprintf(fnew,"\n \n");
 for(int i=1;i<=SizeOfMatrix+1;i++) 
  fprintf(fnew," %lf ",e[i]);
 fprintf(fnew,"\n \n");    
 fclose(fnew);  
 f=fopen(NameOfOutput,"a");
 if(NumberOfAnswer==1)
  fprintf(f,"\n \n    SizeOfMatrix   NumberOfMatrix   e ");
 if(NumberOfAnswer<10)
  fprintf(f,"\n  %d      %d               %d        " , NumberOfAnswer,SizeOfMatrix,NumberOfMatrix);
 else
  fprintf(f,"\n %d      %d               %d        " , NumberOfAnswer,SizeOfMatrix,NumberOfMatrix);
 for(int i=1;i<=SizeOfMatrix+1;i++)
  fprintf(f,"  %lf",e[i]);
 fprintf(f,"\n NewLine    "); 
 for(int i=1;i<=SizeOfMatrix;i++)
   if(M1[SizeOfMatrix+1][i]>=0)  fprintf(f,"  %d",M1[SizeOfMatrix+1][i]);
   else fprintf(f," %d",M1[SizeOfMatrix+1][i]);
 fprintf(f,"\n NewColumn  "); 
 for(int i=1;i<=SizeOfMatrix;i++)
   if(M1[i][SizeOfMatrix+1]>=0)  fprintf(f,"  %d",M1[i][SizeOfMatrix+1]);
   else fprintf(f," %d",M1[i][SizeOfMatrix+1]);
 fclose(f);
}


void put_to_List(int M1[40][40]){
 Length_of_List++;
 for(int i=1;i<=SizeOfMatrix+1;i++)
  for(int j=1;j<=SizeOfMatrix+1;j++)
   List[Length_of_List][i][j]=M1[i][j];
 List[Length_of_List][0][0]=NumberOfAnswer;
}

bool is_equal(int M1[9][9], int M2[40][40]){
 int i,j,a,b,c,d;
 a=0; b=0; c=0; d=0;
 for(i=1;i<=SizeOfMatrix+1;i++)
  for(j=1;j<=SizeOfMatrix+1;j++){
   a+=(M1[i][j]-M2[i][j])*(M1[i][j]-M2[i][j]);
   b+=(M1[i][j]+M2[i][j])*(M1[i][j]+M2[i][j]);
   c+=(M1[i][j]-M2[j][i])*(M1[i][j]-M2[j][i]);
   d+=(M1[i][j]+M2[j][i])*(M1[i][j]+M2[j][i]);
   if(((a>0)&&(b>0))&&((c>0)&&(d>0)))
    return false; 
 }
 return true;
}

bool is_new_in_List(int M1[40][40]){
 for(int j=1;j<=Length_of_List;j++)
  if(is_equal(List[j],M1))
    return false; 
 return true;
}

void print_matrix_display(int Matr[40][40]){
 for(int i=1;i<=SizeOfMatrix+1;i++){
  printf(" \n       ");
  for(int j=1;j<=SizeOfMatrix+1;j++)
   printf("     %d",Matr[i][j]);
 }
} 

void perest(){         /*permutations*/                  
 int n,fa,x,y,fe,r,ff,per[40];
 int M2[40][40];
 copy_matrix(Matrix,M3,SizeOfMatrix+1);
 n=SizeOfMatrix+1;
 for(fa=1;fa<=n;fa++)
  per[fa]=fa;
 if(is_new_in_List(M3))
   put_to_List(M3);
  fa=2;
  while(fa>0){
   fa=2;
   x=n;
   while(x>1){
    if(per[x]>per[x-1]){
     if(x<n){
      y=n;
      while((per[y]<per[x-1])&&(y>=x))
       y--;
      change(&per[x-1],&per[y]);
      fe=x-1;
      r=y;
      change_(&fe,&r);
      for(ff=x;ff<=n;ff++)
       for(y=ff+1;y<=n;y++)
	if(per[ff]>per[y]){
	 change(&per[ff],&per[y]);
	 fe=ff;
	 r=y;
	 change_(&fe,&r);
	}
     }
     else{
      change(&per[n],&per[n-1]);
      fe=n;
      r=n-1;
      change_(&fe,&r);
     }
     if(is_new_in_List(M3))
      put_to_List(M3);
     x=0;
     fa=1;
    }
    else
     x--;
   }
   if((x<=1)&&(fa==2))
    fa=0;
 }
}

int sgn(int a){
  if(a>0)  return 1;
  if(a==0) return 0;
  if(a<0)  return -1; 
}

void mutation(int M1[40][40],int k){
 int M2[40][40];
 copy_matrix(M1,M2,SizeOfMatrix+1);
 for(int i=1;i<=SizeOfMatrix+1;i++)
  for(int j=1;j<=SizeOfMatrix+1;j++)
    M1[i][j]=-M2[i][j]*(1-abs(sgn((i-k)*(j-k))))+(M2[i][j]+sgn(M2[i][k])*max(0,M2[i][k]*M2[k][j]))*abs(sgn((i-k)*(j-k))); 
}

bool is_admissible(){
 int k;
 k=1;       //compute e[SizeOfMatrix+1]                                  
 while((Matrix[k][SizeOfMatrix+1]==0)&&(k<=SizeOfMatrix))
  k++;
 if(k==SizeOfMatrix+1)
  return false;
 if((Matrix[k][SizeOfMatrix+1]*Matrix[SizeOfMatrix+1][k]<0)&&(Matrix[k][SizeOfMatrix+1]*Matrix[SizeOfMatrix+1][k]>=-4))
  e[SizeOfMatrix+1]=-e[k]*Matrix[SizeOfMatrix+1][k]/Matrix[k][SizeOfMatrix+1];
 else
  return false;
 for(k=1;k<=SizeOfMatrix;k++){
  if(Matrix[k][SizeOfMatrix+1]*Matrix[SizeOfMatrix+1][k]>=-4){
   if(e[k]*Matrix[SizeOfMatrix+1][k]!=-e[SizeOfMatrix+1]*Matrix[k][SizeOfMatrix+1])
    return false;
  }
 }
 return true;
}

bool is_infinite(){
 int k,M1[40][40];
 copy_matrix(Matrix,M1,SizeOfMatrix+1);
 for(int i=1;i<=NumberOfRandomMutations;i++){
  k=(rand() % (SizeOfMatrix+1))+1;
  mutation(M1,k);
  for(int i=1;i<=SizeOfMatrix+1;i++)
   for(int j=1;j<=SizeOfMatrix+1;j++)
    if(abs(M1[i][j]*M1[j][i])>4)
     return true;
 }
 return false;
}


bool is_new(){
 int k,M1[40][40];
 copy_matrix(Matrix,M1,SizeOfMatrix+1);
 for(int i=1;i<=NumberOfRandomMutationsN;i++){
  for(int j=1;j<=Length_of_List;j++)
   if(is_equal(List[j],M1))
    return false;
  k=(rand() % (SizeOfMatrix+1))+1;
  mutation(M1,k);
 }
 return true;
}

void attach(int end_ ){  
 for(int i=-4;i<=4;i++){
  Matrix[SizeOfMatrix+1][end_]=i;
  for(int j=-4;j<=4;j++){ 
   Matrix[end_][SizeOfMatrix+1]=j;
   if(end_>1)
    attach(end_-1);
   else {
    Matrix[SizeOfMatrix+1][SizeOfMatrix+1]=0;
    if(is_admissible()) 
     if(!is_infinite())
      if(is_new()){
       NumberOfAnswer++;
       perest();
       //put_to_List(Matrix);
       print_last_line_column(Matrix);
      }       
   }
  }
 }
}

int main(){
 NumberOfRandomMutations=3000;
 NumberOfRandomMutationsN=600;
 printf("\nPrint input filename:  ");
 scanf("%s", NameOfInput);
 file=fopen(NameOfInput,"r");
 printf("\nPrint output filename:  ");
 scanf("%s", NameOfOutput);
 f=fopen(NameOfOutput,"w"); 
 fclose(f);
 fnew=fopen("input_next.txt","w"); 
 fclose(fnew);
 NumberOfMatrix=0;
 Length_of_List=0;
 while (!feof(file)){
  NumberOfAnswer=0;
  read_matrix();
  NumberOfMatrix++;
  print_matrix();
  attach(SizeOfMatrix);
 } 
 fclose(file);
 printf("\n Finished \n");
 return 0;
}