#include <stdio.h>
#include <stdlib.h>

typedef struct RESULT_T {
    long sqsize, sqx, sqy, sqline;
    } result_t;

inline long pw(long n, int p) {
  long nn = 1;
  if (p == 0) return 1;
  int c = 0;
  while (c < p) {
    nn *= n;
    c++;
  }
  return nn;
}

long filesizecr(char filename[], long *crpos)
{
  char buf[300000];
  unsigned long fs = 0, size = 1;
  *crpos = -1;
  FILE *fp;
  if ((fp = fopen(filename, "rb")) == NULL) return -1;

  while (size > 0) {
    size = fread(&buf, 1, sizeof(buf), fp);
    if (*crpos == -1) {
      long c = 0;
      while (c < size) {
        if ((buf[c] == '\n') && (*crpos == -1)) *crpos = (long) fs + c;
        c++;
      }
    }
    fs += size;
  }
  fclose(fp);
  return fs;
}

typedef struct SQUARE_FINDER {
  long pos;
  long isSquare;
  long size;
} finder_t;

inline void findLargestSquareHere(long * h, result_t *t, long len, long nlen) {
  long i;
  finder_t f;
  f.pos = 0;
  while (f.pos < len) {
    f.size = h[f.pos];
      while (f.size > t->sqy) {
            f.isSquare = nlen - (f.pos + f.size);
            i = f.pos;
            while ((f.isSquare >= 0) && (i < f.pos + f.size)) {
        f.isSquare = h[i] - f.size;
        i++;
        }
            if ((f.isSquare >= 0) && (f.size > t->sqy)) {
              t->sqx = f.pos;
              t->sqy = f.size;
            }
          f.size--;
      }
    f.pos++;
  }
  t->sqsize = t->sqy * t->sqy;
}

int main(int ac, char **av) {
  long i;
  char cobs, cfree, cfill;
  long firstcrpos = 0;
  if (ac <= 1) {
    printf("Usage %s [filename]\n", av[0]);
    exit(1);
  }
  char * fname = av[1];
  long fsize = filesizecr(fname, &firstcrpos);

  result_t res;
  res.sqx = 0;
  res.sqy = 0;
  res.sqsize = 0;
  res.sqline = 0;

  if (fsize != -1) printf("File size = %lu\n", fsize);
  else {
    printf("Error while opening file!\n");
    exit(0);
  }
  printf("First \\n in file is %ld\n", firstcrpos);

  char *fbuf;
  FILE *fp;
  if ((fp = fopen(fname, "rb")) == NULL) {
    printf("Error while opening file!\n");
    exit(0);
  }

  printf("Mallocing %ld bytes\n", firstcrpos * sizeof(char) + 1);
  fbuf = (char*) malloc(firstcrpos * sizeof(char) + 1);
  long bytesread = fread(fbuf, 1, firstcrpos * sizeof(char), fp);
  printf("Bytes read: %ld\n", bytesread);

  if ((bytesread != firstcrpos * sizeof(char)) || (bytesread < 4)) {
    printf("Error while reading file!\n");
    exit(0);
  }

  fbuf[bytesread] = '\0';
  printf("Header read: %s\n", fbuf);
  cfill = fbuf[bytesread - 1];
  cobs = fbuf[bytesread - 2];
  cfree = fbuf[bytesread - 3];
  fbuf[bytesread - 3] = '\0';
  i = bytesread - 4;
  long cpow = 0;
  long clines = 0;
  while (i >= 0) { // atoi
    if (fbuf[i] > '9' || fbuf[i] < '0') {
      printf("Wrong symbols in lines count");
      exit(0);
    }
    clines +=  (fbuf[i] - '0') * pw(10, cpow);
    cpow++;
    i--;
  }
  printf("Fill [%c], free [%c], obstacle[%c], Lines: %ld\n", cfill, cfree, cobs, clines);

  long linelen = ((fsize - bytesread) / clines) - 1;
  free(fbuf);

  char temp;
  bytesread = fread(&temp, 1, sizeof(char), fp);
  if (temp != '\n') {
    printf("Error while reading file!\n");
    exit(0);
  }

  i = 0;
  long * hysto;
  long * lasthysto;
  lasthysto = (long *) malloc(linelen * sizeof(long));
  long j = 0;
  while (j < linelen) {
    lasthysto[j] = 0;
    j++;
  }
  j = 0;
  while (i < clines) {
    fbuf = (char *) malloc(linelen + 1);
    bytesread = fread(fbuf, 1, linelen + 1, fp);
    if ((fbuf[linelen] != '\n') || (bytesread != linelen + 1)) {
      printf("Error while reading file (%x, %x, %ld)!\n", fbuf[linelen], '\n', bytesread);
      exit(0);
    }
    fbuf[linelen] = '\0';
    hysto = (long *) malloc(linelen * sizeof(long));
    j = 0;
    while (j < linelen) {
      if ((fbuf[j] != cobs) && (fbuf[j] != cfree)) {
        printf("Error (%ld, %x)\n", j, fbuf[j]);
        exit(0);
      }
      if (fbuf[j] == cobs) hysto[j] = 0;
      if (fbuf[j] == cfree) hysto[j] = lasthysto[j] + 1;
      lasthysto[j] = hysto[j];
      j++;
    }
    free(fbuf);
    result_t tres;
    tres.sqsize = 0;
    tres.sqx = 0;
    tres.sqy = res.sqy;
    findLargestSquareHere(hysto, &tres, linelen - tres.sqy, linelen);
    free(hysto);

    if (res.sqsize < tres.sqsize) {
      res.sqsize = tres.sqsize;
      res.sqx = tres.sqx;
      res.sqy = tres.sqy;
      res.sqline = i;
    }
    i++;
  }
  free(lasthysto);
  fclose(fp);

  if ((fp = fopen(fname, "rb")) == NULL) {
    printf("Error while opening file!\n");
    exit(0);
  }

  fbuf = (char*) malloc(firstcrpos * sizeof(char) + 1);
  bytesread = fread(fbuf, 1, firstcrpos * sizeof(char) + 1, fp);
  i = 0;
  while (i < clines) {
    fbuf = (char *) malloc(linelen + 1);
    bytesread = fread(fbuf, 1, linelen + 1, fp);
    if ((fbuf[linelen] != '\n') || (bytesread != linelen + 1)) {
      printf("Error while reading file (%x, %x, %ld)!\n", fbuf[linelen], '\n', bytesread);
      exit(0);
    }
    fbuf[linelen] = '\0';
    j = 0;
    char * linebuf = (char *) malloc (linelen * sizeof(char));
    while (j < linelen) {
      if ((i > res.sqline - res.sqy) && (i <= res.sqline) && (j >= res.sqx) && (j < res.sqx + res.sqy))
        printf("%c", cfill);
      else
        printf("%c", fbuf[j]);
      j++;
    }
    free(fbuf);
    printf("\n");
    i++;
  }
  fclose(fp);
}