#include <fstream>
#include <cstring>
//#include <iostream> //for TESTING

int sizeField;
int cubedSize;
int attackRange;
int allowedFights;
int row;
int column;
int startColumn;
int endColumn;
int startRow;
int endRow;
int startDiag[2];
int endDiag[2];
int c;
int r;
int number[10];
int limiter;

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

int pivot(int a[], int first, int last, int *scoreMatrix)
{
	int  p = first;
	int pivotElement = scoreMatrix[a[first]];

	for (int i = first + 1; i <= last; i++)
	{
		if (scoreMatrix[a[i]] > pivotElement)
		{
			p++;
			swap(a[i], a[p]);
		}
	}

	swap(a[p], a[first]);

	return p;
}

void quickSort(int a[], int first, int last, int *scoreMatrix)
{
	int pivotElement;

	if (first < last)
	{
		pivotElement = pivot(a, first, last, scoreMatrix);
		quickSort(a, first, pivotElement - 1, scoreMatrix);
		quickSort(a, pivotElement + 1, last, scoreMatrix);
	}
}

void fillOverlay(int* overlayMatrix, int row, int column)
{
	//Add the row
	startColumn = column - attackRange;
	if (startColumn < 0)
		startColumn = 0;

	endColumn = column + attackRange;
	if (endColumn >= sizeField)
		endColumn = sizeField - 1;

	for (c = startColumn; c <= endColumn; c++)
		overlayMatrix[sizeField*row + c]++;

	//Add the column
	startRow = row - attackRange;
	if (startRow < 0)
		startRow = 0;

	endRow = row + attackRange;
	if (endRow >= sizeField)
		endRow = sizeField - 1;

	for (r = startRow; r <= endRow; r++)
		overlayMatrix[sizeField*r + column]++;

	//Add the top left to bottom right diagonal
	//First the beginning of the diagonal
	if ((row - startRow) <= (column - startColumn))
	{
		startDiag[0] = startRow;
		startDiag[1] = column - (row - startRow);
	}
	else
	{
		startDiag[1] = startColumn;
		startDiag[0] = row - (column - startColumn);
	}

	//Now the end
	if ((endRow - row) <= (endColumn - column))
	{
		endDiag[0] = endRow;
		endDiag[1] = column + (endRow - row);
	}
	else
	{
		endDiag[1] = endColumn;
		endDiag[0] = row + (endColumn - column);
	}

	//And now we sum the row
	c = startDiag[1];
	for (r = startDiag[0]; r <= endDiag[0]; r++)
	{
		overlayMatrix[sizeField*r + c]++;
		c++;
	}

	//Add the bottom left to top right diagonal
	//First the beginning of the diagonal
	if ((endRow - row) <= (column - startColumn))
	{
		startDiag[0] = endRow;
		startDiag[1] = column - (endRow - row);
	}
	else
	{
		startDiag[1] = startColumn;
		startDiag[0] = row + (column - startColumn);
	}

	//Now the end
	if ((row - startRow) <= (endColumn - column))
	{
		endDiag[0] = startRow;
		endDiag[1] = column + (row - startRow);
	}
	else
	{
		endDiag[1] = endColumn;
		endDiag[0] = row - (endColumn - column);
	}

	//And now we sum the row
	c = startDiag[1];
	for (r = startDiag[0]; r >= endDiag[0]; r--)
	{
		overlayMatrix[sizeField*r + c]++;
		c++;
	}
}


int recursiveCheck(int* scoreMatrix, int* positionMatrix, int* overlayMatrix, int* scoreList, int fights, long int* score, int position, int iteration)
{
	position++;
	if (position == cubedSize)
		return 1;

	int row;
	int column;

	int* positionTemp = new int[cubedSize];
	int* overlayTemp = new int[cubedSize];
	int* positionInit = new int[cubedSize];
	long int tempScore;
	int tempFights;
	long int scoreInit = *score;
	int endWhile = limiter*iteration*1.5;

	if (endWhile > cubedSize)
		endWhile = cubedSize;

	std::memcpy(positionInit, positionMatrix, cubedSize*sizeof(positionInit));

	iteration++;

	while (position < endWhile)
	{
		row = scoreList[position] / sizeField;
		column = scoreList[position] % sizeField;
		tempFights = fights + overlayMatrix[sizeField*row + column];
		if (tempFights <= allowedFights)
		{
			std::memcpy(overlayTemp, overlayMatrix, cubedSize*sizeof(overlayTemp));
			fillOverlay(overlayTemp, row, column);
			std::memcpy(positionTemp, positionInit, cubedSize*sizeof(positionTemp));
			positionTemp[sizeField*row + column] = 1;
			tempScore = scoreMatrix[sizeField*row + column] + scoreInit;

			recursiveCheck(scoreMatrix, positionTemp, overlayTemp, scoreList, tempFights, &tempScore, position, iteration);

			if (tempScore > *score)
			{
				*score = tempScore;
				std::memcpy(positionMatrix, positionTemp, cubedSize*sizeof(positionTemp));
			}
		}
		position++;
	}

	delete[] positionTemp;
	delete[] overlayTemp;
	delete[] positionInit;

	return 0;
}

int main()
{
	std::ifstream inputFile;
	inputFile.open("queens.in");

	inputFile >> sizeField;

	cubedSize = sizeField*sizeField;

	int* inputMatrix = new int[cubedSize];

	inputFile >> attackRange;

	inputFile >> allowedFights;

	int sum;
	int largest;

	//Fill the input matrix with the initial values
	for (row = 0; row < sizeField; row++)
	{
		for (column = 0; column < sizeField; column++)
		{
			inputFile >> inputMatrix[sizeField*row + column];
		}
	}

	if (sizeField <= 6)
	{
		limiter = cubedSize - 1;
	}
	else if (sizeField < 12)
	{
		limiter = 2;
	}
	else
	{
		limiter = 1;
	}

	/*//TESTING
	for (row = 0; row < sizeField; row++)
	{
		for (column = 0; column < sizeField; column++)
		{
			std::cout << inputMatrix[sizeField*row + column] << "|";
		}
		std::cout << std::endl;
	}*/

	//Fill the score matrix we use to add the scores
	int* scoreMatrix = new int[cubedSize];

	for (row = 0; row < sizeField; row++)
	{
		for (column = 0; column < sizeField; column++)
		{
			std::memset(number, 0, sizeof(number));
			sum = 0;
			//Add the row
			startColumn = column - attackRange;
			if (startColumn < 0)
				startColumn = 0;

			endColumn = column + attackRange;
			if (endColumn >= sizeField)
				endColumn = sizeField - 1;

			for (c = startColumn; c <= endColumn; c++)
			{
				sum = sum + inputMatrix[sizeField*row + c];
				number[inputMatrix[sizeField*row + c]]++;
			}
			//Add the column
			startRow = row - attackRange;
			if (startRow < 0)
				startRow = 0;

			endRow = row + attackRange;
			if (endRow >= sizeField)
				endRow = sizeField - 1;

			for (r = startRow; r <= endRow; r++)
			{
				sum = sum + inputMatrix[sizeField*r + column];
				number[inputMatrix[sizeField*r + column]]++;
			}
			//Add the top left to bottom right diagonal
				//First the beginning of the diagonal
			if ((row - startRow) <= (column - startColumn))
			{
				startDiag[0] = startRow;
				startDiag[1] = column - (row - startRow);
			}
			else
			{
				startDiag[1] = startColumn;
				startDiag[0] = row - (column - startColumn);
			}

				//Now the end
			if ((endRow - row) <= (endColumn - column))
			{
				endDiag[0] = endRow;
				endDiag[1] = column + (endRow - row);
			}
			else
			{
				endDiag[1] = endColumn;
				endDiag[0] = row + (endColumn - column);
			}

				//And now we sum the row
			c = startDiag[1];
			for (r = startDiag[0];  r <= endDiag[0]; r++)
			{
				sum = sum + inputMatrix[sizeField*r + c];
				number[inputMatrix[sizeField*r + c]]++;
				c++;
			}

			//Add the bottom left to top right diagonal
			//First the beginning of the diagonal
			if ((endRow - row) <= (column - startColumn))
			{
				startDiag[0] = endRow;
				startDiag[1] = column - (endRow - row);
			}
			else
			{
				startDiag[1] = startColumn;
				startDiag[0] = row + (column - startColumn);
			}

			//Now the end
			if ((row - startRow) <= (endColumn - column))
			{
				endDiag[0] = startRow;
				endDiag[1] = column + (row - startRow);
			}
			else
			{
				endDiag[1] = endColumn;
				endDiag[0] = row - (endColumn - column);
			}

			//And now we sum the row
			c = startDiag[1];
			for (r = startDiag[0]; r >= endDiag[0]; r--)
			{
				sum = sum + inputMatrix[sizeField*r + c];
				number[inputMatrix[sizeField*r + c]]++;
				c++;
			}
			largest = 0;
			for (int numIt = 1; numIt <= 9; numIt++)
			{
				if (number[numIt] > largest)
					largest = number[numIt];
			}

			//add to matrix and go to next field
			scoreMatrix[sizeField*row + column] = sum*largest;

		}
	}

	//Now that we have the score matrix, we no longer need the input matrix
	delete[] inputMatrix;

	//We make a pointer array to hold the priority
	int *scoreList = new int[cubedSize];

	for (int point = 0; point < cubedSize; point++)
	{
		scoreList[point] = point;
	}

	//We use a quick sort to order by priority
	
	quickSort(scoreList, 0, (cubedSize - 1), scoreMatrix);

	/*
	//TESTING
	for (int point = 0; point < cubedSize; point++)
	{
		std::cout << scoreMatrix[scoreList[point]] << std::endl;
	}

	std::cout << std::endl;

	for (row = 0; row < sizeField; row++)
	{
		for (column = 0; column < sizeField; column++)
		{
			std::cout << scoreMatrix[sizeField*row + column] << "|";
		}
		std::cout << std::endl;
	}
	*/

	//TODO sort the sums so we can get the higher results quicker

	int* positionMatrix = new int[cubedSize];
	int* positionTemp = new int[cubedSize];
	int* overlayTemp = new int[cubedSize];

	//Now we begin the recursive check
	long int score = 0;
	long int tempScore;
	int tempFights;
	for (int position = 0; position < limiter; position++)
	{
		row = scoreList[position] / sizeField;
		column = scoreList[position] % sizeField;

		std::memset(overlayTemp, 0, cubedSize*sizeof(overlayTemp));
		std::memset(positionTemp, 0, cubedSize*sizeof(positionTemp));

		positionTemp[sizeField*row + column] = 1;

		fillOverlay(overlayTemp, row, column);

		tempScore = scoreMatrix[sizeField*row + column];
		tempFights = 0;

		recursiveCheck(scoreMatrix, positionTemp, overlayTemp, scoreList, tempFights, &tempScore, position, 2);

		if (tempScore > score)
		{
			score = tempScore;
			std::memcpy(positionMatrix, positionTemp, cubedSize*sizeof(positionTemp));
		}
	}


	std::ofstream outputFile;
	outputFile.open("queens.out");
	for (row = 0; row < sizeField; row++)
	{
		for (column = 0; column < sizeField; column++)
		{
			if (positionMatrix[sizeField*row + column] == 1)
			{
				outputFile << row+1 << char(32) << column+1 << '\n';
			}
		}
	}

	return 0;