#include <stdio.h>
#include <limits.h> 

#include <iostream>
#include <cstdio>
#include <ctime>

#define __TEST_PERFORMANCE 0

#if __TEST_PERFORMANCE == 1
// for QueryPerformanceFrequency
#include <Windows.h>
#endif

__int64 freq, tStart, tStop;
unsigned long TimeDiff;

int maxsolutions  = 40;
int solutionCounter = 0;
int sizeSolutionsArray = 19*10;
int  * solutionsArray = NULL;
//// Get the frequency of the hi-res timer
//QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
//// Assuming that has worked you can then use hi-res timer
//QueryPerformanceCounter((LARGE_INTEGER*)&tStart);
//// Perform operations that require timing
//QueryPerformanceCounter((LARGE_INTEGER*)&tStop);
//// Calculate time difference
//TimeDiff = (unsigned long)(((tStop - tStart) * 1000000) / freq);

int * data = NULL;
int * x = NULL;
int * tmp = NULL;

inline void parsePermutation (int n, int m, int * rindx,int *results) {

	int i =0,j=0;
	for (i=0; i<n;i++)
		data[i] = i+1;
	for (i=0; i<m;i++) {
		results[i] = data[rindx[i]-1];
		for (j=rindx[i]-1; j<n-1; j++) {
			data[j] = data[j+1];
		}
	}
	//	delete [] data; data = NULL;
}
inline bool getXs(int n,int *inputs, int * rs) {
	bool flag = false;
	//	int * x = new int [n+1];

	x[10]=inputs[0], x[11]=inputs[1], x[14]=inputs[2], x[15]=inputs[3], x[16]=inputs[4], x[18]=inputs[5], x[19]=inputs[6];
	x[17] = 38 -x[18] -x[19];
	x[13] = 38 - x[14] - x[15] - x[16];
	x[12] = 38 - x[16] - x[19];
	x[8] =  38 -x[13] - x[17];
	x[9] = 38 - x[8] - x[10] - x[11] - x[12];
	x[7] = 38 -x[11] -x[15] -x[18];
	x[3] = 38 - x[7] -x[12];
	x[6] = 38 - x[3] - x[10]- x[14]- x[17];
	x[5] = x[6] -x[9] +x[11] -x[13] +x[16];
	x[4] = 38 -x[9] -x[14] -x[18];
	x[1] = 38 -x[5] -x[10] -x[15] -x[19];
	x[2] = 38-x[1]-x[3];

	int i = 0;
	for (i=0; i<n+1; i++) 
		rs[i] = x[i];
	//	delete []x ; x= NULL;
	return false;
}
inline void printxs(int n,int * xs) {
	//printf ("\n xs: ");
	int i = 0;
	printf ("\n");
	for (i =1;i <= n+1;i++)  {
		printf("%d,",xs[i-1]);
		if (i >0 && (i%5  == 0))
			printf ("\n");
	}
}

inline void testEqs(int * x) {

	int eq1 = x[1] + x[2] + x[3] ;
	int eq2 = x[4] + x[5] + x[6] + x[7];
	int eq3 = x[8] + x[9] + x[10] + x[11] + x[12];
	int eq4 = x[13] + x[14] + x[15] + x[16] ;
	int eq5 = x[17] + x[18] + x[19];
	int eq6 = x[1] + x[4] + x[8] ;
	int eq7 = x[2] + x[5] + x[9] + x[13] ;
	int eq8 = x[3] + x[6] + x[10] + x[14] + x[17] ;
	int eq9 = x[7] + x[11] + x[15] + x[18];
	int eq10 = x[12] + x[16] + x[19] ;
	int eq11 = x[8] + x[13] + x[17] ;
	int eq12 = x[4] + x[9] + x[14] + x[18] ;
	int eq13 = x[1] + x[5] + x[10] + x[15] + x[19];
	int eq14 = x[2] + x[6] + x[11] + x[16];
	int eq15 = x[3] + x[7] + x[12] ;

	printf("\nEQs\n",eq1);
	printf("EQ1: %d\n",eq1);
	printf("EQ2: %d\n",eq2);
	printf("EQ3: %d\n",eq3);
	printf("EQ4: %d\n",eq4);
	printf("EQ5: %d\n",eq5);
	printf("EQ6: %d\n",eq6);
	printf("EQ7: %d\n",eq7);
	printf("EQ8: %d\n",eq8);
	printf("EQ9: %d\n",eq9);
	printf("EQ10: %d\n",eq10);
	printf("EQ11: %d\n",eq11);
	printf("EQ12: %d\n",eq12);
	printf("EQ13: %d\n",eq13);
	printf("EQ14: %d\n",eq14);
	printf("EQ15: %d\n",eq15);
}


inline bool testXs(int n, int * x, int * rs ) {
	//	int * tmp = new int [n+1];
	int i = 0;
	for (i = 0; i<= n ;i++) 
		tmp[i] = -1;
	bool tmpflag = true;
	for (i = 1; i<= n ;i++) {
		if ( x[i] <= n && x[i] >= 1) {
			if (tmp[ x[i] ] == -1) {
				tmp[ x[i] ] = x[i];
			} else {
				tmpflag = false;
				break;
			}
		} else {
			tmpflag = false;
			break;
		}
	}
	if (tmpflag == false) {
		//delete [] tmp ;
		//tmp = NULL;
		//printxs(n,tmp);
		return false;
	} else {
		for (i = 1; i<= n ;i++) {
			if (tmp[ i ] == -1 || tmp[ i ] != i) {
				tmpflag = false;
				break;
			}
			rs[i-1]= x[i];
		}
		//delete [] tmp ;
		//tmp = NULL;

		if (tmpflag == false) {
			//printxs(n,tmp);
			return false;
		} else {
			//printxs(n,tmp);
			return true;
		}
	}
}
inline void createIndices(int n, int m, int k, int * rindx) {
	int i = 0,dsi =1,j=0;
	for (i=0; i<m; i++) {
		dsi = (k) %(n-i);
		if (dsi==0) 
			dsi = n-i;
		rindx[i] = dsi;
		if (k<= n-i) {
			for (j = i+1;j<m;j++)
				rindx[j] = 1;
			break;
		} 
		//k = (k-1) /(n-i+1);
		k = (k-1)/(n-i)+1;
	}
}
void main() {

#if __TEST_PERFORMANCE == 1
	QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
	// Assuming that has worked you can then use hi-res timer
	QueryPerformanceCounter((LARGE_INTEGER*)&tStart);
#endif

	//std::clock_t start;
	//double diff;

	//start = std::clock();
	//  for ( int i = 0; i < 1000000; i++ )
	//    printf ( "iamthwee" );


	//int maxsolutions  = 10;
	//int solutionCounter = 0;
	//int sizeSolutionsArray = 19*10
	int total = 1,m=7,n=19;
	int i = 0,j=0;

	sizeSolutionsArray = n*maxsolutions;
	solutionsArray = new int[sizeSolutionsArray];
	for (i = 0;i <sizeSolutionsArray;i++)
		solutionsArray[i] = 0;

	printf("Signed int min: %d max: %d\n",INT_MIN, INT_MAX);


	total = 1;
	for (i = 1; i<= m; i++) {
		total *= (n-i+1); 
	}
	printf("total: %d \n",total);

	//indexpermutation (4,2);
	i = 1;
	int * indxs = new int[m];
	int * results = new int[m];
	int * results2 = new int[n+1];
	int * results3 = new int[n];

	data = new int[n];
	x = new int [n+1];
	tmp = new int [n+1];

	bool b = false;

//#pragma omp parallel for
	for (i =1; i<=total;i++) {
		createIndices(n,m,i, indxs) ;
		//if (i%17*16*15*14*13==0)
		//	printf("%d\n",i);
		parsePermutation (n,m,indxs,results);
		//printf("\n ====");
		//for(j=0; j<m;j++) {
		//	printf("%d,",results[j]);
		//}
		getXs(n,results, results2);
		//printf("\n Results2");
		//printxs(n,results2);

		b = testXs(n,  results2, results3 ); 
		//printf("\n Results3");
		//printxs(n-1,results3);

		if (b) {
			//printf("\nTrue %d",i);
			//printf("\nResults");
			//printxs(n-1,results3);
			int ib =0;
			//			printf("\n solutionCounter %d",solutionCounter);
			if (solutionCounter < maxsolutions) {
				for (ib =0;ib < n;ib++) {
					//printf("\n solutionCounter*n+ib%d, solutionsArray[solutionCounter*n+ib] %d, results3[ib] %d",solutionCounter*n+ib,solutionsArray[solutionCounter*n+ib], results3[ib]);
					solutionsArray[solutionCounter*n+ib] = results3[ib];
				}
				solutionCounter++;
			}
			//printf("\n solutionCounter %d data\n",solutionCounter);
			//printxs(n-1,solutionsArray + (solutionCounter-1)*n);
			//testEqs(results2);
			//break;
		}
		else {
			//printf("\nFalse");
			//printxs(n-1,results2);
		}
		//if (i % 10000000 ==0 ) {
		//	printf ("\nProgress %d:",i);
		//	//diff = ( std::clock() - start ) / (double)CLOCKS_PER_SEC;
		//	//printf ("\nTime elapsed: %10.5f",diff);
		//}
	}
	//if (solutionCounter <= maxsolutions) {
	int ib =0;
	printf("\nTotal solutions %d\n",solutionCounter);
	for (ib =0;ib < solutionCounter;ib++) {
		printf("\nSolution No.%d\n",ib+1);
		//solutionsArray[solutionCounter*n+ib] = results3[ib];
		printxs(n-1,solutionsArray+ib*n);

		//solutionCounter++;
	}
	//}

#if __TEST_PERFORMANCE == 1
	//diff = ( std::clock() - start ) / (double)CLOCKS_PER_SEC;
	//printf ("\nTotal time elapsed: %10.5f",diff);
	QueryPerformanceCounter((LARGE_INTEGER*)&tStop);
	// Calculate time difference
	TimeDiff = (unsigned long)(((tStop - tStart) * 1000000) / freq);
	printf ("\nTotal time elapsed: %ld",TimeDiff);
#endif

}
/*
void parsePermutation (int n, int m, int * rindx,int *results) {
int * data = new int[n];
int i =0,j=0;
for (i=0; i<n;i++)
data[i] = i+1;
for (i=0; i<m;i++) {
results[i] = data[rindx[i]-1];
for (j=rindx[i]-1; j<n-1; j++) {
data[j] = data[j+1];
}
//printf ("\n-----");
//for (j=0; j<n; j++) {
//	//data[j] = data[j+1];
//	printf("%d,",data[j]);
//}
}
delete [] data; data = NULL;
}

bool getXs(int n,int *inputs, int * rs) {
//if (inputs[0]+inputs[1] >= 36) {
//	return false;
//}
//if (inputs[1]+inputs[4] >= 37) {
//	return false;
//}
//if (inputs[6]+inputs[4] >= 38) {
//	return false;
//}
//if (inputs[6]+inputs[5] >= 38) {
//	return false;
//}
//if (inputs[5]+inputs[2] >= 37) {
//	return false;
//}
//if (inputs[0]+inputs[2] >= 36) {
//	return false;
//}
//if (inputs[2]+inputs[3]+inputs[4] >= 38) {
//	return false;
//}
//if (inputs[0]+inputs[3]+inputs[6] >= 37) {
//	return false;
//}
//if (inputs[1]+inputs[3]+inputs[5] >= 38) {
//	return false;
//}
bool flag = false;
int * x = new int [n+1];

x[10]=inputs[0], x[11]=inputs[1], x[14]=inputs[2], x[15]=inputs[3], x[16]=inputs[4], x[18]=inputs[5], x[19]=inputs[6];

x[17] = 38 -x[18] -x[19];
x[13] = 38 - x[14] - x[15] - x[16];
x[12] = 38 - x[16] - x[19];
x[8] =  38 -x[13] - x[17];
x[9] = 38 - x[8] - x[10] - x[11] - x[12];
x[7] = 38 -x[11] -x[15] -x[18];
x[3] = 38 - x[7] -x[12];
x[6] = 38 - x[3] - x[10]- x[14]- x[17];
x[5] = x[6] -x[9] +x[11] -x[13] +x[16];
x[4] = 38 -x[9] -x[14] -x[18];
x[1] = 38 -x[5] -x[10] -x[15] -x[19];
x[2] = 38-x[1]-x[3];

//int x1 = 76 -x10 -x11 -x14 -2*x15-x16 -x18 -x19;
//int x2 = x10 +x14 +x15;
//int x3 = -38 +x11 +x15+x16 +x18 +x19;
//int x4 = x10+ x11 +15;
//int x5 = -38 + x11+x14+x15 +x16 +x18;
//int x6 = 38 - x10 - x11- x14- x15 -x16;
//int x7 = 38 -x11 -x15 -x18;
//int x8 = -38 +x14 + x15 +x16 +x18 +x19;
//int x9 = 38 - x10 - x11 - x14 - x15 - x18;

//printf("\n%d__%d__%d",x[1],x[2],x[3]);
//printf("\n%d__%d__%d__%d",x[4],x[5],x[6],x[7]);
//printf("\n%d__%d__%d__%d__%d",x[8],x[9],x[10],x[11],x[12]);
//printf("\n%d__%d__%d__%d",x[13],x[14],x[15],x[16]);
//printf("\n%d__%d__%d",x[17],x[18],x[19]);


//int eq1 = x[1] + x[2] + x[3] ;
//int eq2 = x[4] + x[5] + x[6] + x[7];
//int eq3 = x[8] + x[9] + x[10] + x[11] + x[12];
//int eq4 = x[13] + x[14] + x[15] + x[16] ;
//int eq5 = x[17] + x[18] + x[19];
//int eq6 = x[1] + x[4] + x[8] ;
//int eq7 = x[2] + x[5] + x[9] + x[13] ;
//int eq8 = x[3] + x[6] + x[10] + x[14] + x[17] ;
//int eq9 = x[7] + x[11] + x[15] + x[18];
//int eq10 = x[12] + x[16] + x[19] ;
//int eq11 = x[8] + x[13] + x[17] ;
//int eq12 = x[4] + x[9] + x[14] + x[18] ;
//int eq13 = x[1] + x[5] + x[10] + x[15] + x[19];
//int eq14 = x[2] + x[6] + x[11] + x[16];
//int eq15 = x[3] + x[7] + x[12] ;

//     0     0     0     1     1     1     1     0     0     0     0     0     0     0     0     0     0     0     0
//     1     0     0     1     0     0     0     1     0     0     0     0     0     0     0     0     0     0     0
//printf("\nEQs\n",eq1);
//printf("EQ1: %d\n",eq1);
//printf("EQ2: %d\n",eq2);
//printf("EQ3: %d\n",eq3);
//printf("EQ4: %d\n",eq4);
//printf("EQ5: %d\n",eq5);
//printf("EQ6: %d\n",eq6);
//printf("EQ7: %d\n",eq7);
//printf("EQ8: %d\n",eq8);
//printf("EQ9: %d\n",eq9);
//printf("EQ10: %d\n",eq10);
//printf("EQ11: %d\n",eq11);
//printf("EQ12: %d\n",eq12);
//printf("EQ13: %d\n",eq13);
//printf("EQ14: %d\n",eq14);
//printf("EQ15: %d\n",eq15);
int i = 0;
for (i=0; i<n+1; i++) 
rs[i] = x[i];
delete []x ; x= NULL;
return false;
}
void printxs(int n,int * xs) {
//printf ("\n xs: ");
int i = 0;
printf ("\n");
for (i =1;i <= n+1;i++)  {
printf("%d,",xs[i-1]);
if (i >0 && (i%5  == 0))
printf ("\n");
}
}

void testEqs(int * x) {

int eq1 = x[1] + x[2] + x[3] ;
int eq2 = x[4] + x[5] + x[6] + x[7];
int eq3 = x[8] + x[9] + x[10] + x[11] + x[12];
int eq4 = x[13] + x[14] + x[15] + x[16] ;
int eq5 = x[17] + x[18] + x[19];
int eq6 = x[1] + x[4] + x[8] ;
int eq7 = x[2] + x[5] + x[9] + x[13] ;
int eq8 = x[3] + x[6] + x[10] + x[14] + x[17] ;
int eq9 = x[7] + x[11] + x[15] + x[18];
int eq10 = x[12] + x[16] + x[19] ;
int eq11 = x[8] + x[13] + x[17] ;
int eq12 = x[4] + x[9] + x[14] + x[18] ;
int eq13 = x[1] + x[5] + x[10] + x[15] + x[19];
int eq14 = x[2] + x[6] + x[11] + x[16];
int eq15 = x[3] + x[7] + x[12] ;

printf("\nEQs\n",eq1);
printf("EQ1: %d\n",eq1);
printf("EQ2: %d\n",eq2);
printf("EQ3: %d\n",eq3);
printf("EQ4: %d\n",eq4);
printf("EQ5: %d\n",eq5);
printf("EQ6: %d\n",eq6);
printf("EQ7: %d\n",eq7);
printf("EQ8: %d\n",eq8);
printf("EQ9: %d\n",eq9);
printf("EQ10: %d\n",eq10);
printf("EQ11: %d\n",eq11);
printf("EQ12: %d\n",eq12);
printf("EQ13: %d\n",eq13);
printf("EQ14: %d\n",eq14);
printf("EQ15: %d\n",eq15);
}


bool testXs(int n, int * x, int * rs ) {
int * tmp = new int [n+1];
int i = 0;
for (i = 0; i<= n ;i++) 
tmp[i] = -1;
bool tmpflag = true;
for (i = 1; i<= n ;i++) {
if ( x[i] <= n && x[i] >= 1) {
if (tmp[ x[i] ] == -1) {
tmp[ x[i] ] = x[i];
} else {
tmpflag = false;
break;
}
} else {
tmpflag = false;
break;
}
}
if (tmpflag == false) {
delete [] tmp ;
tmp = NULL;
//printxs(n,tmp);
return false;
} else {
for (i = 1; i<= n ;i++) {
if (tmp[ i ] == -1 || tmp[ i ] != i) {
tmpflag = false;
break;
}
rs[i-1]= x[i];
}
delete [] tmp ;
tmp = NULL;

if (tmpflag == false) {
//printxs(n,tmp);
return false;
} else {
//printxs(n,tmp);
return true;
}
}
}



void createIndices(int n, int m, int k, int * rindx) {
int i = 0,dsi =1,j=0;
for (i=0; i<m; i++) {
dsi = (k) %(n-i);
if (dsi==0) 
dsi = n-i;
rindx[i] = dsi;
if (k<= n-i) {
for (j = i+1;j<m;j++)
rindx[j] = 1;
break;
} 
//k = (k-1) /(n-i+1);
k = (k-1)/(n-i)+1;
}
//printf("\n");
//for (i=0; i<m; i++) 
//	printf("%d,",rindx[i]);
}


void main() {
printf("Signed int min: %d max: %d\n",INT_MIN, INT_MAX);
int total = 1,m=7,n=19;

int i = 0,j=0;
total = 1;
for (i = 1; i<= m; i++) {
total *= (n-i+1); 
}
printf("total: %d \n",total);

//indexpermutation (4,2);
i = 1;
int * indxs = new int[m];
int * results = new int[m];
int * results2 = new int[n+1];
int * results3 = new int[n];

bool b = false;


for (i =1; i<=total;i++) {
createIndices(n,m,i, indxs) ;
//if (i%17*16*15*14*13==0)
//	printf("%d\n",i);
parsePermutation (n,m,indxs,results);
//printf("\n ====");
//for(j=0; j<m;j++) {
//	printf("%d,",results[j]);
//}
getXs(n,results, results2);
//printf("\n Results2");
//printxs(n,results2);

b = testXs(n,  results2, results3 ); 
//printf("\n Results3");
//printxs(n-1,results3);

if (b) {
printf("\nTrue %d",i);
printf("\nResults");
printxs(n-1,results3);
//testEqs(results2);
//break;
}
else {
//printf("\nFalse");
//printxs(n-1,results2);
}
//if (i >=1000000 ) {
//	printf("\nWe test 1000000");
//	break;
//}
//if (i >=1 ) {
//	//printf("\nWe test 1000000");
//	break;
//}
// 253955520
//  10000000  
if (i % 10000000 ==0 ) {
printf ("\nProgress %d:",i);
}
}

//printf("\n Test conditions \n");
//int * xs = new int[n+1];
//bool b = false;
////xs[0] = -1;xs[1] = 1;xs[2] = 5;xs[3] = 3;xs[4] = 6;
////xs[5] = 18;xs[6] = 11;xs[7] = -1;xs[8] = 4;xs[9] = -1;
////xs[10] = 2;xs[11] = -1;xs[12] = 15;xs[13] = 17;xs[14] = -1;
////xs[15] = 2;xs[16] = 5;xs[17] = 5;xs[18] = -1;xs[19] = 23;
////printxs(n,xs);
////b = testXs(n,  xs, results2 ); 
////if (b) {
////	printf("\nTrue");
////	printxs(n-1,results2);
////}
////else 
////	 printf("\nFalse");

//xs[0] = -1;xs[1] = 1;xs[2] = 2;xs[3] = 4;xs[4] = 3;
//xs[5] = 5;xs[6] = 6;xs[7] = 7;xs[8] = 8;xs[9] = 9;
//xs[10] = 10;xs[11] = 11;xs[12] = 12;xs[13] = 13;xs[14] = 14;
//xs[15] = 15;xs[16] = 16;xs[17] = 17;xs[18] = 18;xs[19] = 19;
//printf("\nXs");
//printxs(n,xs);
//b = testXs(n,  xs, results2 ); 
//if (b) {
//	printf("\nTrue");
//	printf("\nResults");
//	printxs(n-1,results2);
//}
//else {
//	 printf("\nFalse");
//		//printxs(n-1,results2);
//}

//xs[0] = -1;xs[1] = 1;xs[2] = 2;xs[3] = 4;xs[4] = 4;
//xs[5] = 5;xs[6] = 6;xs[7] = 7;xs[8] = 8;xs[9] = 9;
//xs[10] = 10;xs[11] = 11;xs[12] = 12;xs[13] = 13;xs[14] = 14;
//xs[15] = 15;xs[16] = 16;xs[17] = 17;xs[18] = 18;xs[19] = 19;
//printf("\nXs");
//printxs(n,xs);
//b = testXs(n,  xs, results2 ); 
//if (b) {
//	printf("\nTrue");
//	printf("\nResults");
//	printxs(n-1,results2);
//}
//else {
//	 printf("\nFalse");
//		//printxs(n-1,results2);
//}

//xs[0] = -1;xs[1] = 1;xs[2] = 2;xs[3] = 4;xs[4] = 3;
//xs[5] = 5;xs[6] = 6;xs[7] = 7;xs[8] = 8;xs[9] = 9;
//xs[10] = 10;xs[11] = 11;xs[12] = 12;xs[13] = 13;xs[14] = 14;
//xs[15] = 15;xs[16] = 16;xs[17] = 17;xs[18] = 20;xs[19] = 19;
//printf("\nXs");
//printxs(n,xs);
//b = testXs(n,  xs, results2 ); 
//if (b) {
//	printf("\nTrue");
//	printf("\nResults");
//	printxs(n-1,results2);
//}
//else {
//	 printf("\nFalse");
//		//printxs(n-1,results2);
//}


}
*/
/*
int main()
{
std::clock_t start;
double diff;

start = std::clock();
for ( int i = 0; i < 1000000; i++ )
printf ( "iamthwee" );
diff = ( std::clock() - start ) / (double)CLOCKS_PER_SEC;

std::cout<<"printf: "<< diff <<'\n';
}#include <iostream>
#include <cstdio>
#include <ctime>

int main()
{
std::clock_t start;
double diff;

start = std::clock();
for ( int i = 0; i < 1000000; i++ )
printf ( "iamthwee" );
diff = ( std::clock() - start ) / (double)CLOCKS_PER_SEC;

std::cout<<"printf: "<< diff <<'\n';
}
*/