Spajder Đura se nekako našao na Novom Beogradu. Nakon što je ponovo spasao svet od uništenja, rešio je da ruča. Spajder Đura, naravno najviše voli ćevape, i to u velikim količinama. Novi Beograd je, kao što je svima poznato, podeljen na blokove (N x N), i u svakom bloku se nalazi po jedna ćevabdžinica. Spajder Đuri su poznate cene ćevapa u svakom od blokova. Međutim, kako je Spajder Đura umoran, on može da preleti (kačeći se o zgrade, pomoću paukove mreže) najviše K blokova. Iz svakog bloka, on može da skoči (preleti) na bilo koji od osam susednih (znači može da se kreće dijagonalno).

Spajder Đura je čuo da se u Beogradu održava Mala olimpijada pa je rešio da takmičare priupita za pomoć, ne bi li pojeo najviše moguće ćevapa, to jest našao najjeftiniju ćevabdžinicu u okolini u kojoj se nalazi. Na nesreću, Spajder Đura ne zna gde se trenutno nalazi, pa takmičari moraju da za svaki blok pronađu najjeftiniju ćevabdžinicu udaljenu najviše K blokova.

Vaš zadatak je da za unetu matricu, koja predstavlja cene ćevapa u svakom od blokova, odredite matricu istih dimenzija čiji elementi predstavljaju najnižu cenu ćevapa u svim blokovima do kojih se može stići sa najviše K skokova (letenja).

Ulaz:

U tekstualnom faju spider.in se u prvom redu nalaze brojevi N i K, (1 ≤ N ≤ 2000, 1 ≤ K ≤ N). Zatim se u narednih N redova nalazi matrica veličine N x N, i to u svakom redu po N celih brojeva iz intervala [0..2000000000].

Izlaz:

U tekstualni fajl spider.out u N redova ispisati matricu dimenzija N x N (koja predstavlja rešenje goreopisanog problema), i to u svakom od N redova po N brojeva razmaknutih blanko znakom.

Primer:

4 1
1 2 3 4 
6 5 4 3
2 3 4 5
8 7 6 5

1 1 2 3
1 1 2 3
2 2 3 3
2 2 3 4

#include <stdio.h>
#include <vector>

#define MAX_N     2000
#define MAX_PRICE 2000000000L

using namespace std;

int Prefix[MAX_N*2], Suffix[MAX_N*2];

vector<int>& LinearMin(vector<int> &A, int k) {

  vector<int> &Sol = *(new vector<int>(A.size()));
  
  for (int i=0;i<A.size();i++) 
    Suffix[i] = (i%(2*k+1)==0)?A[i]:min(Suffix[i-1], A[i]);
  
  Prefix[A.size()-1] = A[A.size()-1];
  for (int i=A.size()-2;i>=0;i--)
    Prefix[i] = ((i+1)%(2*k+1)==0)?A[i]:min(Prefix[i+1], A[i]);
  
  for (int i=0;i<A.size();i++)
    Sol[i] = min((i-k>=0)?Prefix[i-k]:Suffix[i],(i+k<A.size())?Suffix[i+k]:Prefix[i]);
  
  return Sol;
}

int main() {
  FILE *fin, *fout;

  fin = fopen("spider.in", "r");
  fout = fopen("spider.out", "w");
  
  int n, k;  
  fscanf(fin, "%d %d", &n, &k);
  vector<int> A(n+k), Sol[MAX_N];

  for (int j=0;j<n;j++) {

    for (int i=0;i<n;i++) 
      fscanf(fin, "%d", &A[i]);
    for (int i=0;i<k;i++)
      A[i+n] = MAX_PRICE;

    vector<int> LineSol = LinearMin(A, k);
    for (int i=0;i<n;i++) 
      Sol[i].push_back(LineSol[i]);
  }

  for (int i=0;i<n;i++) {
    for (int j=0;j<k;j++)
      Sol[i].push_back(MAX_PRICE);
    Sol[i] = LinearMin(Sol[i], k);
  }
    
  for (int j=0;j<n;j++) {
    for (int i=0;i<n;i++) 
      fprintf(fout, "%d ", Sol[i][j]);
    fprintf(fout, "\n");
  }
  fclose(fin);
  fclose(fout);
}

#include <stdio.h>
#include <vector>
#include <map>

#define MAX_N     2000
#define MAX_PRICE 2000000000L

using namespace std;

vector<int>& RBTreeMin(vector<int> &A, int k) {

  vector<int> &Sol = *(new vector<int>(A.size()));

  map<int, int> M;

  for (int i=0;i<A.size()+k;i++) {
    if (i<A.size())
      M[A[i]]++;
    if (i > 2*k) {
      M[A[i-2*k-1]]--;
      if (M[A[i-2*k-1]] == 0)
  M.erase(A[i-2*k-1]);
    }
    if (i >= k)
      Sol[i-k] = M.begin()->first;
  }

  return Sol;
}


int main() {

  FILE *fin, *fout;
  fin = fopen("spider.in", "r");
  fout = fopen("spider.out", "w");
  
  int n, k;  
  fscanf(fin, "%d %d", &n, &k);
  vector<int> A(n), Sol[MAX_N];

  for (int j=0;j<n;j++) {

    for (int i=0;i<n;i++) 
      fscanf(fin, "%d", &A[i]);

    vector<int> LineSol = RBTreeMin(A, k);
    for (int i=0;i<n;i++) 
      Sol[i].push_back(LineSol[i]);
  }

  for (int i=0;i<n;i++)
    Sol[i] = RBTreeMin(Sol[i], k);
    
  for (int j=0;j<n;j++) {
    for (int i=0;i<n;i++) 
      fprintf(fout, "%d ", Sol[i][j]);
    fprintf(fout, "\n");
  }
  fclose(fin);
  fclose(fout);
}

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

#define MAX_N     2000
#define MAX_PRICE 2000000000L

using namespace std;

int Mat[MAX_N][MAX_N], SolX[MAX_N][MAX_N], SolY[MAX_N][MAX_N];

int main() {

  int n, k;  
  scanf("%d %d", &n, &k);

  for (int j=0;j<n;j++)
    for (int i=0;i<n;i++) 
      scanf("%d", &Mat[j][i]);

  for (int j=0;j<n;j++)
    for (int i=0;i<n;i++) {
      SolX[j][i] = Mat[j][i];
      for (int l=max(0,i-k);l<min(n,i+k+1);l++) 
  SolX[j][i] <?= Mat[j][l];
    }
  

  for (int j=0;j<n;j++)
    for (int i=0;i<n;i++) {
      SolY[i][j] = SolX[i][j];
      for (int l=max(0,i-k);l<min(n,i+k+1);l++)
  SolY[i][j] <?= SolX[l][j];
    }


  for (int j=0;j<n;j++) {
    for (int i=0;i<n;i++) 
      printf("%d ", SolY[j][i]);
    printf("\n");
  }
}