#include <iostream>
#include <ctime>
#include <iomanip>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <fstream>
using namespace std;

int **board = NULL;
int **boardConflicts = NULL;
int conflicts = 0;
int allowedMoves = 50;
int N = 3;
long long int finalScore = 0;


class CellScore
{
public:
	unsigned long score;
	int indexI;
	int indexJ;
	map<int, int> setOfNumbers;

	CellScore(int i, int j) : setOfNumbers()
	{
		indexI = i;
		indexJ = j;
		score = 0;
	}

	void FillSet();
};

void CellScore::FillSet()
{
	map<int, int>::iterator it;
	setOfNumbers[board[indexI][indexJ]] = 4;

	for (int i = 1; i <= allowedMoves; i++)
	{
		/*if (indexJ + i >= N && indexJ - i < 0)
		{
		break;
		}*/

		if (indexJ + i < N || indexJ - i >= 0)
		{
			//right
			if (indexJ + i < N)
			{
				it = setOfNumbers.find(board[indexI][indexJ + i]);
				if (it == setOfNumbers.end())
				{
					setOfNumbers[board[indexI][indexJ + i]] = 1;
				}
				else
				{
					setOfNumbers[board[indexI][indexJ + i]]++;
				}
			}
			//left
			if (indexJ - i >= 0)
			{
				it = setOfNumbers.find(board[indexI][indexJ - i]);
				if (it == setOfNumbers.end())
				{
					setOfNumbers[board[indexI][indexJ - i]] = 1;
				}
				else
				{
					setOfNumbers[board[indexI][indexJ - i]]++;
				}
			}

			//top and down
			if (indexI - i >= 0 || indexI + i < N)
			{
				//top
				if (indexI - i >= 0)
				{
					it = setOfNumbers.find(board[indexI - i][indexJ]);
					if (it == setOfNumbers.end())
					{
						setOfNumbers[board[indexI - i][indexJ]] = 1;
					}
					else
					{
						setOfNumbers[board[indexI - i][indexJ]]++;
					}
				}

				//down
				if (indexI + i < N)
				{
					it = setOfNumbers.find(board[indexI + i][indexJ]);
					if (it == setOfNumbers.end())
					{
						setOfNumbers[board[indexI + i][indexJ]] = 1;
					}
					else
					{
						setOfNumbers[board[indexI + i][indexJ]]++;
					}
				}
			}


			//top left
			if (indexI - i >= 0 && indexJ - i >= 0)
			{
				it = setOfNumbers.find(board[indexI - i][indexJ - i]);
				if (it == setOfNumbers.end())
				{
					setOfNumbers[board[indexI - i][indexJ - i]] = 1;
				}
				else
				{
					setOfNumbers[board[indexI - i][indexJ - i]]++;
				}
			}

			//top right
			if (indexI - i >= 0 && indexJ + i < N)
			{
				it = setOfNumbers.find(board[indexI - i][indexJ + i]);
				if (it == setOfNumbers.end())
				{
					setOfNumbers[board[indexI - i][indexJ + i]] = 1;
				}
				else
				{
					setOfNumbers[board[indexI - i][indexJ + i]]++;
				}
			}

			//down right
			if (indexI + i < N && indexJ + i < N)
			{
				it = setOfNumbers.find(board[indexI + i][indexJ + i]);
				if (it == setOfNumbers.end())
				{
					setOfNumbers[board[indexI + i][indexJ + i]] = 1;
				}
				else
				{
					setOfNumbers[board[indexI + i][indexJ + i]]++;
				}
			}


			//down left
			if (indexI + i < N && indexJ - i >= 0)
			{
				it = setOfNumbers.find(board[indexI + i][indexJ - i]);
				if (it == setOfNumbers.end())
				{
					setOfNumbers[board[indexI + i][indexJ - i]] = 1;
				}
				else
				{
					setOfNumbers[board[indexI + i][indexJ - i]]++;
				}
			}
		}

	}

	int max = 0;
	it = setOfNumbers.begin();
	while (it != setOfNumbers.end())
	{
		if (max < it->second)
		{
			max = it->second;
		}
		score += (it->second) * (it->first);
		it++;
	}

	score *= max;
}

bool CellComparer(CellScore *a, CellScore *b)
{
	return (a->score > b->score);

}

void setQueenFightZone(CellScore const *cell)
{
	boardConflicts[cell->indexI][cell->indexJ] = 999;
	for (int i = 1; i <= allowedMoves; i++)
	{
		/*if (indexJ + i >= N && indexJ - i < 0)
		{
		break;
		}*/

		if (cell->indexJ + i < N || cell->indexJ - i >= 0)
		{
			//right
			if (cell->indexJ + i < N)
			{
				boardConflicts[cell->indexI][cell->indexJ + i]++;
			}
			//left
			if (cell->indexJ - i >= 0)
			{
				boardConflicts[cell->indexI][cell->indexJ - i]++;
			}

			//top and down
			if (cell->indexI - i >= 0 || cell->indexI + i < N)
			{
				//top
				if (cell->indexI - i >= 0)
				{
					boardConflicts[cell->indexI - i][cell->indexJ]++;
				}

				//down
				if (cell->indexI + i < N)
				{
					boardConflicts[cell->indexI + i][cell->indexJ]++;
				}
			}


			//top left
			if (cell->indexI - i >= 0 && cell->indexJ - i >= 0)
			{
				boardConflicts[cell->indexI - i][cell->indexJ - i]++;
			}

			//top right
			if (cell->indexI - i >= 0 && cell->indexJ + i < N)
			{
				boardConflicts[cell->indexI - i][cell->indexJ + i]++;
			}

			//down right
			if (cell->indexI + i < N && cell->indexJ + i < N)
			{
				boardConflicts[cell->indexI + i][cell->indexJ + i]++;
			}


			//down left
			if (cell->indexI + i < N && cell->indexJ - i >= 0)
			{
				boardConflicts[cell->indexI + i][cell->indexJ - i]++;
			}
		}

	}
}

void placeQueensGreedy(vector<CellScore *> &queenScore)
{
	
	ofstream outFile("queens.out");
	int maxConflicts = conflicts;

	vector<CellScore *>::iterator it;
	it = queenScore.begin();
	while (it != queenScore.end())
	{
		if (boardConflicts[(*it)->indexI][(*it)->indexJ] == 0)
		{
			setQueenFightZone((*it));
			finalScore += (*it)->score;
			//it = queenScore.begin();
			outFile << (*it)->indexI+1 << " " << (*it)->indexJ+1 << endl;
			//std::cout << (*it)->indexI + 1 << " " << (*it)->indexJ + 1 << " Score:" << (*it)->score << endl;
			it++;
		}
		else
		{
			it++;
		}
	}



	it = queenScore.begin();
	while (it != queenScore.end())
	{
		if (boardConflicts[(*it)->indexI][(*it)->indexJ] < 999 && boardConflicts[(*it)->indexI][(*it)->indexJ]++ < maxConflicts && maxConflicts - (++boardConflicts[(*it)->indexI][(*it)->indexJ]) >= 0)
		{
			maxConflicts -= boardConflicts[(*it)->indexI][(*it)->indexJ]++;
			setQueenFightZone((*it));
			finalScore += (*it)->score;
			//it = queenScore.begin();
			outFile << (*it)->indexI + 1 << " " << (*it)->indexJ + 1 << endl;
			//std::cout << (*it)->indexI + 1 << " " << (*it)->indexJ + 1 << " Score:" << (*it)->score << endl;
			it++;
		}
		else
		{
			it++;
		}
	}

	outFile.close();
}

int main()
{
	clock_t start = clock();

	ifstream inputFile("queens.in");

	int n = 0;
	int r = 0;
	int k = 0;
	//std::cout << "Enter a value for N:";
	//cin >> n;
	
	inputFile >> n;
	inputFile >> r;
	inputFile >> k;
	
	N = n;
	allowedMoves = r;
	conflicts = k;
	board = new int*[n];
	boardConflicts = new int*[n];
	for (int i = 0; i < n; i++)
	{
		board[i] = new int[n];
		boardConflicts[i] = new int[n];
	}

	srand(time(NULL));

	CellScore *cscore = NULL;
	vector<CellScore *> boardScore;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//board[i][j] = (rand() % 50) + 1;
			inputFile >> board[i][j];
			boardConflicts[i][j] = 0;
		}
	}


	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cscore = new CellScore(i, j);
			cscore->FillSet();
			boardScore.push_back(cscore);
		}
	}

	/*
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//std::cout << board[i][j] << " ";
		}
		//std::cout << "\n";
	}


	std::cout << "\n";
	*/
	
	std::sort(boardScore.begin(), boardScore.end(), CellComparer);
	placeQueensGreedy(boardScore);
	/*
	std::cout << "\n";
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			std::cout << boardConflicts[i][j] << " ";
		}
		std::cout << "\n";
	}

	vector<CellScore *>::iterator vcs = boardScore.begin();
	while (vcs != boardScore.end())
	{
		//cout << "(" << (*vcs)->indexI << "," << (*vcs)->indexJ << "):" << (*vcs)->score << endl;
		vcs++;
	}
	*/
	
	

	delete cscore;
	for (int i = 0; i < n; i++)
	{
		delete[] board[i];
		delete[] boardConflicts[i];
	}
	delete[] board;
	delete[] boardConflicts;

	clock_t end = clock();

	//std::cout << "Finished:" << fixed << ((float)(end - start)) / CLOCKS_PER_SEC << " Score:" << finalScore << endl;
	//std::system("pause");
	return 0;