var fs = require('fs');
var createInterface = require('readline').createInterface;
var createReadStream = fs.createReadStream;
var EOL = require('os').EOL;
var slices = [];
var heatMatrix = [];

var files = [
  'example',
  'small',
  'medium',
  'big',
];

var rectangularPlots = [
  [2, 3],
  [3, 2],
  [5, 1],
  [1, 5],
];

var file = files[1];

var lineReader = createInterface({
  input: createReadStream('in/' + file + '.in'),
});

class Pizza {
  constructor() {
    this.rows = 0;
    this.cols = 0;
    this.l = 0;
    this.max = 0;
    this.cells = [];
    this.all = [];
    this.slices = [];
  }

  log() {
    console.log(EOL);
    for (var y = 0; y < this.rows; y += 1) {
      for (var x = 0; x < this.cols; x += 1) {
        process.stdout.write(this.getCell(x, y).busy ? 'X' : 'O');
      }
      console.log(EOL);
    }
  }

  getCell(x, y) {
    if (x < 0 || y < 0 || x >= this.cols || y >= this.rows) return null;
    return this.cells[y][x];
  }

  takeSlice(cell, w, h) {
    const cells = [];
    const ingredients = { M: 0, T: 0 };
    for (var x = cell.x; x < cell.x + w; x += 1) {
      for (var y = cell.y; y < cell.y + h; y += 1) {
        const cell = this.getCell(x, y);
        if (!cell || cell.busy) return null;
        ingredients[cell.t] += 1;
        cells.push(cell);
      }
    }
    if (ingredients.M < this.l || ingredients.T < this.l) return null;
    cells.forEach((c) => { c.busy = true; });
    this.slices.push({
      cells,
      out: [cell.y, cell.x, cell.y + h - 1, cell.x + w - 1],
    });
  }
}

var pizza = new Pizza();

var count = 0;

function readDescLine(line) {
  var values = line.split(' ');
  pizza.rows = parseInt(values[0], 10);
  pizza.cols = parseInt(values[1], 10);
  pizza.l = parseInt(values[2], 10);
  pizza.max = parseInt(values[3], 10);
}

class Cell {
  constructor(x, y, t) {
    this.x = x;
    this.y = y;
    this.t = t;
    this.busy = false;
  }
}

function readPizzaLine(line) {
  var pieces = line.split('');
  pizza.cells.push(pieces.map((piece, x) => {
    const cell = new Cell(x, pizza.cells.length, piece);
    pizza.all.push(cell);
    return cell;
  }));
}

function divisors(n) {
  var c = [];
  var map = {};
  for (var i = 1; i < n; i++) {
    if (n % i === 0) {
      var f = i;
      var s = n / i;
      if (!map[`${f}-${s}`]) {
        map[`${f}-${s}`] = true;
        c.push([f, s]);
      }
      if (!map[`${s}-${f}`]) {
        map[`${s}-${f}`] = true;
        c.push([s, f]);
      }
    }
  }
  return c;
}

function shuffle(a) {
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

function makeCountArray(type, lessIngridient) {
  var array = [];
  var count = 0;
  if (type === 'r') {
    for (var i = 0; i < pizza.rows; i++) {
      for (var j = 0; j < pizza.cols; j++) {
        if (pizza.cells[i][j].t === lessIngridient) {
          count++;
        }
      }
      array[i] = count;
      count = 0;
    }
  }
  else if (type === 'c') {
    for (var i = 0; i < pizza.cols; i++) {
      for (var j = 0; j < pizza.rows; j++) {
        if (pizza.cells[j][i].t === lessIngridient) {
          count++;
        }
      }
      array[i] = count;
      count = 0;
    }
  }
  return array;
}

function getValue(x, array) {
  if (x >= 0 && x < array.length)
    return array[x];
  else return 0;
}
function calculateHeatMatrix(columnArray, rowArray) {
  for (var i = 0; i < rowArray.length; i++) {
    heatMatrix[i] = [];
    for (var j = 0; j < columnArray.length; j++) {
      heatMatrix[i][j] = rowArray[i] + getValue(1 + i, rowArray) + getValue(i - 1, rowArray) + columnArray[j] + getValue(j + 1, columnArray) + getValue(j - 1, columnArray);
    }
  }
}

function findLowest() {
  var lowestValue = 999999;
  var xIndex = 0;
  var yIndex = 0;
  for (var i = 0; i < heatMatrix.length; i++) {
    for (var j = 0; j < heatMatrix[i].length; j++) {
      if (heatMatrix[i][j] != -1 && lowestValue > heatMatrix[i][j]) {
        lowestValue = heatMatrix[i][j];
        xIndex = i;
        yIndex = j;
      }
    }
  }
  return [xIndex, yIndex];
}
function findBiggest(starti, imax, startj, jmax) {
  var bigestValue = -1;
  var xIndex = 0;
  var yIndex = 0;
  for (var i = starti; i <= imax; i++) {
    for (var j = startj; j <= jmax; j++) {
      if (heatMatrix[i][j] != -1 && bigestValue <= heatMatrix[i][j]) {
        bigestValue = heatMatrix[i][j];
        xIndex = i;
        yIndex = j;
      }
    }
  }
  return [xIndex, yIndex];
}
class Slice {
  constructor(x, y, endx, endy) {
    this.startx = x;
    this.starty = y;
    this.endx = endx;
    this.endy = endy;
    this.busy = true;
  }
  log() {
    [this.startx, this.starty, this.endx, this.endy];
  }
}
function findBest(i, imax, j, jmax, x, y, oldSlice) {
  let [sliceEndX, sliceEndY] = findBiggest(i, imax, j, jmax);
  var slice = new Slice(x, y, sliceEndX, sliceEndY);

  if(oldSlice != null && slice.startx === oldSlice.startx && slice.starty === oldSlice.starty &&slice.endx === oldSlice.endx &&slice.endy === oldSlice.endy)
  {
    let [lowestX, lowestY] = findLowest();
    additionalSlice = getRectangualar(lowestX, lowestY, rectangularPlots[3]);
    // if(slice.startx === additionalSlice.startx && slice.starty === additionalSlice.starty &&slice.endx === additionalSlice.endx &&slice.endy === additionalSlice.endy)
    {
      console.log("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
        return null;
    }
  }
  //console.log("slice:" + x, y, sliceEndX, sliceEndY);
  if (x >= sliceEndX && y >= sliceEndY) {
    if (isSliceGood(sliceEndX, sliceEndY, x, y)) {
      console.log("good");
      markHeatMapWithslices(sliceEndX, sliceEndY, x, y);
    }
    else {
      heatMatrix[sliceEndX][sliceEndY] = 0;
      slice = findBest(i, imax, j, jmax, x, y, slice);
    }
  }
  else if (x <= sliceEndX && y <= sliceEndY) {
    if (isSliceGood(x, y, sliceEndX, sliceEndY)) {
      console.log("good");
      markHeatMapWithslices(x, y, sliceEndX, sliceEndY);
    }
    else {
      heatMatrix[sliceEndX][sliceEndY] = 0;
      slice = findBest( i, imax, j, jmax,x, y, slice);
    }
  }
  else if (x >= sliceEndX && y <= sliceEndY) {
    if (isSliceGood(sliceEndX, y, x, sliceEndY)) {
      console.log("good");
      markHeatMapWithslices(sliceEndX, y, x, sliceEndY);
    }
    else {
      heatMatrix[sliceEndX][sliceEndY] = 0;
      slice = findBest( i, imax, j, jmax,x, y, slice);
    }
  }
  else if (x <= sliceEndX && y >= sliceEndY) {
    if (isSliceGood(x, sliceEndY, sliceEndX, y)) {
      console.log("good");
      markHeatMapWithslices(x, sliceEndY, sliceEndX, y);
    }
    else {
      heatMatrix[sliceEndX][sliceEndY] = 0;
      slice = findBest( i, imax, j, jmax,x, y, slice);
    }
  }
  return slice;
}
function getRectangualar(x, y, plot) {
  var maxX = plot[0] - 1;
  var maxY = plot[1] - 1;
  var sum = 0;

  //  var rectangularCells = [];
  //  rectangularCells.push(new Coordinate(x, y));

  var i = x - maxX > 0 ? x - maxX : 0;
  var imax = x + maxX < pizza.rows ? x + maxX : pizza.rows - 1;
  var j = y - maxY > 0 ? y - maxY : 0;
  var jmax = y + maxY < pizza.cols ? y + maxY : pizza.cols - 1;
  console.log(i, imax, j, jmax);

  return findBest(i, imax, j, jmax, x, y, null);

}
function markHeatMapWithslices(startX, startY, sliceEndX, sliceEndY) {
  for (var i = startX; i <= sliceEndX; i++) {
    for (var j = startY; j <= sliceEndY; j++) {
      heatMatrix[i][j] = -1;
    }
  }
}

function isSliceGood(startX, startY, sliceEndX, sliceEndY) {
  var countT = 0;
  var countM = 0;
  for (var i = startX; i <= sliceEndX; i++) {
    for (var j = startY; j <= sliceEndY; j++) {
      if(heatMatrix[i][j] === 1)
        return false;
      if (pizza.cells[i][j].t === 'T') {
        countT++;
      }
      else if (pizza.cells[i][j].t === 'M') {
        countM++;
      }
    }
  }
  if (countT < pizza.l || countM < pizza.l)
    return false;
  else return true;
}
function start() {

  var mushrooms = pizza.all.filter(c => c.t === 'M').length;
  var tomatoes = pizza.all.length - mushrooms;
  const lessIngridient = mushrooms >= tomatoes ? 'T' : 'M';
  console.log('mushrooms/tomatoes', mushrooms, tomatoes);

  let rowCountArray = makeCountArray('r', lessIngridient);
  let columnCountArray = makeCountArray('c', lessIngridient);

  calculateHeatMatrix(columnCountArray, rowCountArray);

  console.log(heatMatrix);

  for (var i = 0; i < 8; i++) {
    let j = 0;
    let [lowestX, lowestY] = findLowest();
    console.log(lowestX, lowestY);
    var slice = getRectangualar(lowestX, lowestY, rectangularPlots[2]);
     if(slice != null)
     {
      slices[i] = slice
     }
    console.log(heatMatrix);
  }
  /*
   [lowestX, lowestY] = findLowest(heatMatrix);
   [heatMatrix, slices[1]] = getRectangualar(heatMatrix, lowestX, lowestY, rectangularPlots[1]);
   console.log(heatMatrix);
   [lowestX, lowestY] = findLowest(heatMatrix);
   [heatMatrix, slices[2]] = getRectangualar(heatMatrix, lowestX, lowestY, rectangularPlots[1]);
   console.log(heatMatrix);
   */
  /*  var divs = [];
    for (var i = pizza.max; i >= pizza.l*2; i--) {
      divs = divs.concat(divisors(i));
    }

    pizza.all.forEach((cell) => {
      divs.forEach((d) => {
        var w = d[0];
        var h = d[1];
        pizza.takeSlice(cell, w, h);
      })
    });
  */
  points();
  write();
}

function points() {
  console.log(slices.length);
  for (var i = 0; i < slices.length; i++) {
    console.log(slices[i].startx, slices[i].starty, slices[i].endx, slices[i].endy);
  }
  //console.log('points', pizza.all.filter(c => c.busy).length, pizza.all.length);
}

function write() {
  var out = `${slices.length}`;
  slices.forEach(slice => {
    out = `${out}
${slice.startx} ${slice.starty} ${slice.endx} ${slice.endy}`;
  });
  fs.writeFile(`out/${file}.out`, out, () => { });
}

lineReader.on('line', function (line) {
  if (count === 0) readDescLine(line);
  else readPizzaLine(line);
  count++;
  if (count === 1 + pizza.rows) start();
});