You are given a square matrix of size 'n x n'. Each element of the matrix denotes the number of fruits in that cell. You are also given a number 'k' (where 1 <= k <= n).
Consider a square sub-matrix of size 'k x k' inside the given matrix. You are allowed to touch only ONE cell inside this sub-matrix, and when you touch that cell, you get all the fruits of that cell.
Since, you love to eat fruits, you want to touch the cell with maximum number of fruits in the above 'k x k' sub-matrix. Let us call the maximum number of fruits as 'maxFruits' which you can get from this sub-matrix.
Your task is to print the 'maxFruits' for each of the sub-matrices of size 'k x k' inside the given matrix of size 'n x n'.
Input:-
First line contains 't', denoting the number of test cases. Then 't' lines follow, each containing the following:
'n k' (space-separated and without quotes), as explained in the question. Then, 'n' lines each containing 'n' space-separated integers, denoting the number of fruits in each cell (i.e. the input matrix).
Output:-
'n-k+1' lines containing 'n-k+1' space-separated integers denoting 'maxFruits' (explained in question) for all the sub-matrices of size 'k x k'.
Constraints:-
1 <= t <= 30
1 <= k <= n
0 <= (number of fruits in each cell) < 10^9
1 <= n <= 10^3
Problem Setter:-
Devesh Jagwani
None