Distinct Numbers in Sub-Square Submatrices

You are given an \( n \times m \) matrix of integers. You are also given an integer \( k \). Your task is to count the number of distinct integers in every contiguous \( k \times k \) submatrix of the given matrix.

Formally, for each submatrix \( A[i \ldots i+k-1][j \ldots j+k-1] \) (with \( 1 \leq i \leq n-k+1 \) and \( 1 \leq j \leq m-k+1 \)), calculate \( f(i, j) \) where \( f(i, j) \) is the number of distinct integers in that submatrix.

inputFormat

The first line contains three space-separated positive integers ( n ), ( m ), and ( k ) denoting the number of rows, the number of columns, and the size of the sub-square respectively. The next ( n ) lines each contain ( m ) space-separated integers representing the matrix.

outputFormat

Output ( n-k+1 ) lines. Each line should contain ( m-k+1 ) integers separated by a space, where each integer represents the count of distinct numbers in the corresponding ( k \times k ) submatrix.

sample

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

4 4
4 4