Triunghi

Se dă o matrice $A$ de numere naturale, formată din $N$ linii și $M$ coloane. Liniile sunt numerotate de sus în jos de la $0$ la $N - 1$, iar coloanele de la stânga la dreapta de la $0$ la $M - 1$.

Numim triunghiul de mărime $K$ care începe în celula $(i, j)$ mulțimea celulelor la care se poate ajunge plecând din $(i, j)$ și efectuând cel mult $K - 1$ pași în care ne deplasăm cu o celulă în sus sau la dreapta.

Cerință

Pentru fiecare celulă $(i, j)$ cu $K - 1 \leq i < N$ și $0 \leq j < M - K + 1$, vrem să aflăm:

• Valoarea maximă din triunghiul de mărime $K$ care începe în celula $(i, j)$;
• De câte ori apare valoarea maximă din triunghiul de mărime $K$ care începe în celula $(i, j)$ în respectivul triunghi.

Date de intrare

Pe prima linie se găsesc numerele $N, M$ și $K$. Fiecare din următoarele $N$ linii conține câte $M$ numere fiecare. Al $j$-lea număr de pe a $i$-a astfel de linie reprezintă $A_{i, j}$.

Date de ieșire

Se vor afișa două matrice de dimensiuni $(N - K + 1) \times (M - K + 1)$.

Pe fiecare din primele $N - K + 1$ linii se vor afla câte $M - K + 1$ numere naturale. Al $j$-lea număr de pe a $i$-a astfel de linie este valoarea maximă din triunghiul de mărime $K$ care începe în celula $(i - K + 1, j)$.

Pe fiecare din următoarele $N - K + 1$ linii se vor afla câte $M - K + 1$ numere naturale. Al $j$-lea număr de pe a $i$-a astfel de linie este numărul de apariții ale valorii maxime din triunghiul de mărime $K$ care începe în celula $(i - K + 1, j)$ în acest triunghi.

Restricții și precizări

• $1 \leq N, M \leq 3 \ 000$
• $1 \leq K \leq min(N, M)$
• $0 \leq A_{i, j} \leq 1 \ 000 \ 000$ pentru $0 \leq i < N$ și $0 \leq j < M$
• Pentru afișarea corectă a maximului din fiecare triunghi se obține $40\%$ din punctaj.
• Pentru a face citirea și afișarea mai rapidă, recomandăm să folosiți linia: ios_base::sync_with_stdio(false)

Exemplul 1

stdin

4 4 2
1 2 6 14
12 3 13 5
11 4 7 8
10 16 9 15

stdout

12 13 13
12 7 13
16 16 15
1 1 1
1 1 1
1 1 1

Explicație

De exemplu, triunghiul de mărime $= 2$ care începe în $(1, 1)$ este:
$3$
$4 \ 7$
Valoarea maxima este $7$ și apare o singură dată.

În fapt, valoarea maximă din fiecare dintre cele $3 \times 3 = 9$ triunghiuri vizate este unică.

Exemplul 2

stdin

2 3 2
4 5 3
4 4 5

stdout

4 5
3 2

Explicație

Sunt vizate două triunghiuri de mărime $2$.

Primul începe în $(1, 0)$:
$4$
$4 \ 4$
Valoarea maximă este $4$ și apare de $3$ ori.

Al doilea începe în $(1, 1)$:
$5$
$4 \ 5$
Valoarea maximă este $5$ și apare de $2$ ori.