Nabavili smo jednu od super-upijajućih krpi sa jednog od tv shop-ova i želimo da je testiramo. Krpa je pravougaonog oblika i ima šare u obliku vertikalnih i horizontalnih linija koje je dele na n×m podudarnih kvadratića. Test se sastoji od prolivanja mastila na neke od n×m kvadratića krpe (svaki kvadratić je ili uprljan mastilom ili potpuno čist na početku) i merenja vremena za koje će krpa upiti svo mastilo.

Naravno, ispostavlja se da je krpa skupa i beskorisna. Osim xto ne upija leto kako treba, ona doprinosi njegovom razlivanju. Preciznije, svake sekunde leto se razliva na susedne, čiste kvadratiće (tj. svaki čist kvadratić koji u toj sekundi ima bar jednog uprljanog suseda postaje uprljan mastilom) a u isto vreme krpa upija ono što je do tada bilo uprljano mastilom (tj. svaki uprljani kvadratić postaje čist). Dva kvadratića su susedna ako dele zajedničku stranicu.

Pošto smo razočarani krpom, a ne želimo da nam eksperiment propadne, odlučili smo da predvidimo kako će krpa izgledati posle t sekundi.

Ulaz:

(Ulazni podaci se učitavaju iz datoteke mastilo.in.) U prvom redu ulazne datoteke nalaze se 3 prirodna broja n, m i t koji predstavljaju, redom, dimenzije krpe i vreme (u sekundama) posle kog nas interesuje izgled krpe (1 ≤ n, m ≤ 10³, 1 ≤ t ≤ 10⁶). Sledećih n redova sadrže niz od m cifara iz skupa {0, 1} bez razmaka - izgled krpe nakon početnog prolivanja mastila. 1 označava da se na odgovarajućem mestu nalazi uprljan kvadratić, a 0 čist kvadratić.

Izlaz:

(Izlazni podaci se ispisuju u datoteku mastilo.out.) U prvih n redova izlazne datoteke ispisati po m cifara iz skupa {0, 1} bez razmaka - izgled krpe nakon t sekundi. 1 i 0 imaju isto značenje kao na ulazu.

Primer:

4 5 2
01001
00000
10000
00000

01001
00110
10101
01000

Objašnjenje.

Za dati test primer, promena krpe je prikazana na slikama:

Početak	Posle 1 sekunde	Posle 2 sekunde

Napomena.

U 25% test primera biće 1 ≤ n, m, t ≤ 200. Zbog veličine ulaza, C/C++ kodovi bi trebalo da učitavaju cele redove.

#include <cstdlib>
#include <cstdio>

const int MaxN = 1010;
const int inf = 1000000000;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int n, m, t, color;
char s[MaxN];
bool a[MaxN][MaxN], tmp[MaxN][MaxN];
int Qx[MaxN*MaxN], Qy[MaxN*MaxN];
int d[MaxN][MaxN];

bool inside(int x, int y) {
  return (0 <= x && x < n && 0 <= y && y < m);
}

void initialStep() {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      tmp[i][j] = false;
      if (!a[i][j])
        for (int k = 0; k < 4; k++)
          if (inside(i + dx[k], j + dy[k]))
            tmp[i][j] = tmp[i][j] || a[ i + dx[k] ][ j + dy[k] ];
    }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      a[i][j] = tmp[i][j];
}

void BFS() {
  int first = -1, last = 0;
  int x, y, x1, y1;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (a[i][j]) {
        Qx[last] = i;  Qy[last] = j;
        d[i][j] = 0;
        last++;
      }
      else d[i][j] = inf;

  while (first < last - 1) {
    first++;
    x = Qx[first]; y = Qy[first];
    for (int i = 0; i < 4; i++) {
      x1 = x + dx[i];  y1 = y + dy[i];
      if (inside(x1, y1) && d[x1][y1] == inf) {
        d[x1][y1] = d[x][y] + 1;
        Qx[last] = x1;  Qy[last] = y1;
        last++;
      }
    }
  }
}

int main() {

  FILE* inFile = fopen("mastilo.in", "r");
  FILE* outFile = fopen("mastilo.out", "w");

  fscanf(inFile, "%d%d%d", &n, &m, &t);
  for (int i = 0; i < n; i++) {
    fscanf(inFile, "%s", s);
    for (int j = 0; j < m; j++)
      a[i][j] = (s[j] == '1');
  }

  initialStep();
  BFS();

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (d[i][j] > t - 1)
        color = 0;
      else
        color = (t - d[i][j]) % 2;
      if (color == 0) fprintf(outFile, "0");
      else fprintf(outFile, "1");
    }
    fprintf(outFile, "\n");
  }

  fclose(inFile);
  fclose(outFile);
  return 0;
}