Počet bodov:
Popis:  12b
Program:  8b

Za niekoľko desaťročí jeho existencie prišli do Kolosea stovky miliónov divákov. Múry Kolosea tento nápor znášajú veľmi dobre – stoja rovnako pevné a majestátne, ako keď bolo Koloseum nové. Horšie je to s čalúnenými sedačkami. Tie sú už nechutne špinavé a mnohé z nich aj nepríjemne páchnu.

Predavač lístkov Mikix si všimol, že ľudia uprednostňujú miesta, kde je menší smrad. Preto sa Mikix rozhodol, že smrad na jednotlivých miestach zohľadní v cene lístkov.

Úloha

Sektor, v ktorom Mikix predáva lístky, má tvar štvorca s \(n\) radmi po \(n\) sedadiel. Každé sedadlo páchne s nejakou intenzitou, ktorú budeme v tejto úlohe reprezentovať celým číslom (čím väčšie číslo, tým väčší smrad). To, aký silný zápach cítime, keď na sedadle sedíme, však závisí aj od okolitých sedadiel. Konkrétne, vždy cítime najsmradľavejšie sedadlo vo štvorci \(k \times k\) sedadiel so stredom1 v sedadle, na ktorom sedíme.

Mikix chce pre každé sedadlo vo svojom sektore určiť, aký silný smrad je na danom mieste cítiť. Pre každé sedadlo \(S\) teda zistite intenzitu zápachu najsmradľavejšieho sedadla vo štvorci \(k \times k\) okolo sedadla \(S\).

Formát vstupu

Na prvom riadku sa nachádzajú dve kladné celé čísla \(n\) a \(k\) oddelené medzerou, označujúce veľkosť sektora a veľkosť okolia, v ktorom je cítiť zápach. Číslo \(k\) je pritom nepárne. Nasleduje \(n\) riadkov a v nich \(n\) medzerami oddelených celých čísel \(0 \leq a_{i,j} \leq 10^9\) – intenzity zápachu jednotlivých sedadiel.

číslo sady \(1\) \(2\) \(3\) \(4\)
\(n,k \leq\) \(40\) \(100\) \(400\) \(1\,000\)

Formát výstupu

Vypíšte \(n\) riadkov a v každom z nich \(n\) čísel oddelených medzerami. V \(i\)-tom riadku ako \(j\)-te číslo vypíšte intenzitu zápachu najsmradľavejšieho sedadla, ktoré je cítiť zo sedadla \((i,j)\).

Príklady

Input:

3 1
1 2 3
4 5 6
7 8 9

Output:

1 2 3
4 5 6
7 8 9

Cítime iba sedadlo, na ktorom sedíme.

Input:

3 3
1 2 3
4 5 6
7 8 9

Output:

5 6 6
8 9 9
8 9 9

Teraz cítime už aj bezprostredne okolité sedadlá.


  1. číslo \(k\) je nepárne

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.