#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cassert>
#include <cstdlib>
#include <cstring>

using namespace std;

//#define DEBUG_PRINT 1

template <class T>
class Dynamic2DArray
{
public:
  Dynamic2DArray()
    : m_RowsCount(0)
    , m_ColsCount(0)
    , m_Data(nullptr)
  {
  }

  Dynamic2DArray(size_t rowsCount, size_t colsCount)
    : m_RowsCount(rowsCount)
    , m_ColsCount(colsCount)
    , m_Data(new T[rowsCount * colsCount])
  {
  }

  Dynamic2DArray(const Dynamic2DArray<T>& rhs)
    : m_RowsCount(rhs.m_RowsCount)
    , m_ColsCount(rhs.m_ColsCount)
    , m_Data(new T[m_RowsCount * m_ColsCount])
  {
    memcpy(m_Data, rhs.m_Data, sizeof(T) * m_RowsCount * m_ColsCount);
  }

  Dynamic2DArray(Dynamic2DArray<T>&& rhs)
    : m_RowsCount(rhs.m_RowsCount)
    , m_ColsCount(rhs.m_ColsCount)
    , m_Data(rhs.m_Data)
  {
    rhs.m_Data = nullptr;
  }

  Dynamic2DArray& operator=(Dynamic2DArray<T>&& rhs)
  {
    if (this == &rhs)
      return *this;

    m_RowsCount = rhs.m_RowsCount;
    m_ColsCount = rhs.m_ColsCount;
    m_Data = rhs.m_Data;
    rhs.m_Data = nullptr;

    return *this;
  }

  Dynamic2DArray& operator=(const Dynamic2DArray<T>& rhs)
  {
    if (this == &rhs)
      return *this;

    m_RowsCount = rhs.m_RowsCount;
    m_ColsCount = rhs.m_ColsCount;
    m_Data = new T[m_RowsCount * m_ColsCount];
    memcpy(m_Data, rhs.m_Data, sizeof(T) * m_RowsCount * m_ColsCount);

    return *this;
  }

  ~Dynamic2DArray()
  {
    delete[] m_Data;
  }

  T* operator[](int row)
  {
    return m_Data + row * m_ColsCount;
  }

  const T* operator[](int row) const
  {
    return m_Data + row * m_ColsCount;
  }

  void clear()
  {
    memset(m_Data, 0, sizeof(T) * m_RowsCount * m_ColsCount);
  }

  void resize(size_t rowsCount, size_t colsCount)
  {
    m_RowsCount = rowsCount;
    m_ColsCount = colsCount;
    delete[] m_Data;
    m_Data = new T[m_RowsCount * m_ColsCount];
    clear();
  }

  size_t rowsCount() const
  {
    return m_RowsCount;
  }

  size_t colsCount() const
  {
    return m_ColsCount;
  }

private:
  size_t m_RowsCount;
  size_t m_ColsCount;
  T* m_Data;
};

const int8_t SHIFT[8][2] =
{
  int8_t(-1), int8_t(-1),
  int8_t(-1), int8_t( 0),
  int8_t(-1), int8_t(+1),
  int8_t( 0), int8_t(-1),
  int8_t( 0), int8_t(+1),
  int8_t(+1), int8_t(-1),
  int8_t(+1), int8_t( 0),
  int8_t(+1), int8_t(+1)
};

typedef vector<uint16_t> Histogram;

uint8_t g_QueenRange;
uint16_t g_MaxAttackingPairs;
uint8_t g_GenerationsCount;

class Board
{
public:
  Board() : m_MaxValue(0) {}

  void setSize(uint8_t size)
  {
    m_Data.resize(size, size);
    m_Weights.resize(size, size);
    m_Size = size;
  }

  uint8_t getSize() const
  {
    return m_Size;
  }

  void setSquare(uint8_t row, uint8_t col, uint8_t value)
  {
    m_Data[row][col] = value;
    if (value > m_MaxValue)
      m_MaxValue = value;
  }

  uint8_t getSquare(uint8_t row, uint8_t col) const
  {
    return m_Data[row][col];
  }

  void print() const
  {
    cout << "Board size: " << (int)m_Size << endl;
    for (uint8_t r = 0; r < m_Size; ++r)
    {
      for (uint8_t c = 0; c < m_Size; ++c)
        cout << (int)m_Data[r][c] << " ";
      cout << endl;
    }
    cout << endl;
  }

  void printWeights() const
  {
    cout << "Weights: " << endl;
    for (uint8_t r = 0; r < m_Size; ++r)
    {
      for (uint8_t c = 0; c < m_Size; ++c)
        cout << (int)m_Weights[r][c] << " ";
      cout << endl;
    }
    cout << endl;
  }

  void computeWeights()
  {
    for (uint8_t r = 0; r < getSize(); ++r)
    {
      for (uint8_t c = 0; c < getSize(); ++c)
      {
        Histogram histogram(m_MaxValue + 1, 0);

        m_Weights[r][c] = 4 * m_Data[r][c];
        histogram[m_Data[r][c]] += 4;

        for (uint8_t i = 0; i < 8; ++i)
        {
          m_Weights[r][c] += getLineSum(r, c,
            SHIFT[i][0], SHIFT[i][1], histogram);
        }

        uint8_t mostFrequentValue = 0;
        for (uint8_t i = m_MaxValue; i >= 1; --i)
          if (histogram[i] > histogram[mostFrequentValue])
            mostFrequentValue = i;

        m_Weights[r][c] *= histogram[mostFrequentValue];
      }
    }
  }

  uint32_t getWeight(uint8_t row, uint8_t col) const
  {
    return m_Weights[row][col];
  }

private:
  uint16_t getLineSum(uint8_t r, uint8_t c, int8_t rs, int8_t cs,
                      Histogram& histogram)
  {
    uint16_t currentSum = 0;
    assert(g_QueenRange != 0);
    for (uint8_t i = 0; i < g_QueenRange; ++i)
    {
      r += rs; c += cs;
      if (r >= m_Size || c >= m_Size)
        break;
      currentSum += m_Data[r][c];
      ++histogram[m_Data[r][c]];
    }
    return currentSum;
  }

private:
  Dynamic2DArray<uint8_t> m_Data;
  Dynamic2DArray<uint32_t> m_Weights;
  uint8_t m_MaxValue;
  uint8_t m_Size;
};

Board g_Board;

struct Cell
{
  uint8_t row;
  uint8_t column;
};

std::vector<Cell> g_BoardCells;

class Phenotype
{
public:
  Phenotype()
    : m_AttackPairsCount(0)
    , m_Fitness(0)
  {
    uint8_t boardSize = g_Board.getSize();
    m_Queens.resize(boardSize, boardSize);
    m_AttacksCount.resize(boardSize, boardSize);
  }

  Phenotype(uint16_t maxTries) : Phenotype()
  {
    uint8_t boardSize = g_Board.getSize();
    m_Genes.reserve(maxTries);

    for (uint16_t i = 0; i < maxTries; ++i)
    {
      uint8_t r = rand() % boardSize;
      uint8_t c = rand() % boardSize;
      
      injectGene({ r, c });
    }
  }

  void reserve(size_t size)
  {
    m_Genes.reserve(size);
  }

  bool injectGene(Cell gene)
  {
    if(!check(gene.row, gene.column))
      return false;

    m_Genes.push_back(gene);
    m_Queens[gene.row][gene.column] = true;
    m_AttackPairsCount += m_AttacksCount[gene.row][gene.column];
    attack(gene.row, gene.column);
    m_Fitness += g_Board.getWeight(gene.row, gene.column);

    return true;
  }

  void removeLastGene()
  {
    const auto& gene = m_Genes.back();
    m_Fitness -= g_Board.getWeight(gene.row, gene.column);
    attack(gene.row, gene.column, true);
    m_AttackPairsCount -= m_AttacksCount[gene.row][gene.column];
    m_Queens[gene.row][gene.column] = false;
    m_Genes.pop_back();
  }

  uint32_t getFitness() const
  {
    return m_Fitness;
  }

  const vector<Cell>& getGenes() const
  {
    return m_Genes;
  }

private:
  bool check(uint8_t r, uint8_t c)
  {
    if (m_Queens[r][c])
      return false;
    if (m_AttackPairsCount + m_AttacksCount[r][c] > g_MaxAttackingPairs)
      return false;
    return true;
  }

  void attackRow(uint8_t r, uint8_t c, int8_t rs, int8_t cs, bool undo)
  {
    for (uint8_t i = 0; i < g_QueenRange; ++i)
    {
      r += rs; c += cs;
      
      if (r >= g_Board.getSize() || c >= g_Board.getSize())
        break;

      if(undo)
        --m_AttacksCount[r][c];
      else
        ++m_AttacksCount[r][c];
    }
  }

  void attack(uint8_t r, uint8_t c, bool undo = false)
  {
    for (uint8_t i = 0; i < 8; ++i)
      attackRow(r, c, SHIFT[i][0], SHIFT[i][1], undo);
  }

  friend Phenotype crossover(const Phenotype& mother,
                             const Phenotype& father);

private:
  vector<Cell> m_Genes;
  Dynamic2DArray<bool> m_Queens;
  Dynamic2DArray<uint16_t> m_AttacksCount;
  uint16_t m_AttackPairsCount;
  uint32_t m_Fitness;
};

const size_t POPULATION_SIZE = 128;
const size_t CHILDS_COUNT = 2;
const uint8_t MAX_GENERATIONS = 8;
const uint16_t TIME_LIMIT = 4800;

typedef vector<Phenotype> Population;
Population g_Population, g_NextPopulation;
uint32_t g_BestFitness;
vector<Cell> g_BestSolution;

const char* const INPUT_FILE_NAME = "queens.in";
const char* const OUTPUT_FILE_NAME = "queens.out";

void readInput()
{
  FILE* finp = fopen(INPUT_FILE_NAME, "r");

  uint8_t boardSize;
  fscanf(finp, "%hhu %hhu %hu",
    &boardSize, &g_QueenRange, &g_MaxAttackingPairs);
  g_Board.setSize(boardSize);

  uint8_t value;
  for (uint8_t r = 0; r < boardSize; ++r)
    for (uint8_t c = 0; c < boardSize; ++c)
    {
      fscanf(finp, "%hhu", &value);
      g_Board.setSquare(r, c, value);
    }

  fclose(finp);

#ifdef DEBUG_PRINT
  g_Board.print();
#endif
}

void printPopulationFintess(unsigned index, const Population& population)
{
  cout << "Population " << index << ": " << endl;
  for (const auto& phenotype : g_Population)
    cout << phenotype.getFitness() << " ";
  cout << endl;
}

void sortByFitness(Population& population)
{
  sort(population.begin(), population.end(),
    [](const Phenotype& specimen1, const Phenotype& specimen2)
  {
    return specimen1.getFitness() > specimen2.getFitness();
  });
}

Phenotype solveGreedy()
{
  Phenotype solution;
  solution.reserve(g_BoardCells.size());

  for (const auto& cell : g_BoardCells)
  {
    solution.injectGene(cell);
  }

  return solution;
}

void generateInitialPopulation()
{
  uint16_t maxTries = g_Board.getSize() + g_MaxAttackingPairs;
  g_Population.reserve(maxTries);
  g_Population.emplace_back(solveGreedy());

  for (size_t i = 1; i < POPULATION_SIZE; ++i)
  {
    g_Population.emplace_back(maxTries);
  }

  sortByFitness(g_Population);
  g_BestSolution = g_Population[0].getGenes();
  g_BestFitness = g_Population[0].getFitness();

#ifdef DEBUG_PRINT
  printPopulationFintess(0, g_Population);
#endif
}

Phenotype crossover(const Phenotype& mother, const Phenotype& father)
{
  Phenotype child;
  child.m_Genes.reserve(mother.m_Genes.size() + father.m_Genes.size());

  bool isMotherTurn = true;
  for (size_t i = 0; i < mother.m_Genes.size() + father.m_Genes.size(); ++i)
  {
    Cell gene;
    size_t geneIndex;

    if (isMotherTurn)
    {
      geneIndex = rand() % mother.m_Genes.size();
      gene = mother.m_Genes[geneIndex];
    }
    else
    {
      geneIndex = rand() % father.m_Genes.size();
      gene = father.m_Genes[geneIndex];
    }

    child.injectGene(gene);

    isMotherTurn = !isMotherTurn;
  }

  return child;
}

void crossover()
{
  auto breedingSize = g_Population.size() / CHILDS_COUNT;
  for (size_t i = 0; i < breedingSize; ++i)
  {
    for (int k = 0; k < CHILDS_COUNT; ++k)
    {
      auto j = rand() % breedingSize;
      Phenotype individual = crossover(g_Population[i], g_Population[j]);
      g_NextPopulation.emplace_back(individual);
    }
  }

  sortByFitness(g_NextPopulation);
  g_Population = std::move(g_NextPopulation);
  ++g_GenerationsCount;

  if (g_Population[0].getFitness() > g_BestFitness)
  {
    g_BestFitness = g_Population[0].getFitness();
    g_BestSolution = g_Population[0].getGenes();
  }

#ifdef DEBUG_PRINT
  printPopulationFintess(g_GenerationsCount, g_Population);
#endif
}

void initBoardCells()
{
  auto boardSize = g_Board.getSize();
  g_BoardCells.reserve(boardSize * boardSize);

  for (uint8_t r = 0; r < boardSize; ++r)
    for (uint8_t c = 0; c < boardSize; ++c)
      g_BoardCells.push_back({ r, c });

  sort(g_BoardCells.begin(), g_BoardCells.end(),
    [](const Cell& c1, const Cell& c2) {
    return g_Board.getWeight(c1.row, c1.column) >
      g_Board.getWeight(c2.row, c2.column);
  });

#ifdef DEBUG_PRINT
  cout << "Board cells: " << endl;
  for (const auto& cell : g_BoardCells)
  {
    cout << "row = " << (int)cell.row << "; "
      << "column = " << (int)cell.column << "; "
      << "weight = " << g_Board.getWeight(cell.row, cell.column) << endl;
  }
  cout << endl;
#endif
}

void printOutput()
{
  FILE* fout = fopen(OUTPUT_FILE_NAME, "w");
  for (size_t i = 0; i < g_BestSolution.size(); ++i)
    fprintf(fout, "%d %d\n",
      g_BestSolution[i].row + 1, g_BestSolution[i].column + 1);
  fclose(fout);
}

void solveGenetic()
{
  generateInitialPopulation();

#ifdef DEBUG_PRINT
  for (size_t i = 0; i < MAX_GENERATIONS; ++i)
#else
  while (clock() < TIME_LIMIT)
#endif
  {
    crossover();
  }
}

int main()
{
  readInput();
  g_Board.computeWeights();

#ifdef DEBUG_PRINT
  g_Board.printWeights();
#endif

  initBoardCells();
  solveGenetic();
  printOutput();

#ifdef DEBUG_PRINT
  cout << "Best fitness: " << g_BestFitness << endl;
#endif

  return 0;