Submit | All submissions | Best solutions | Back to list |
WPAA - A Mona Lisa (professional) |
- I have a Mona Lisa for sale, you want some?
- I gotta say, it's a nice copy.
- Copy? The museum has a copy! Look, you want it or not?
- Well, it's all great, but why would I need the whole thing? I would take a k x k-millimeter piece.
- OK, I can bill you depending on the number of colours on the piece.
- Then let me know the price for every such piece, and I'll choose myself one that's nice and cheap.
On a n x n-millimeter painting, every square millimetre has a fixed colour. All colours are natural numbers. Your task is to calculate, for every contiguous k x k-millimeter fragment, the number of different colours in this fragment.
Multiple test cases
The first line of the input contains Z ≤ 20 - the number of test cases. Z descriptions of single test cases follow.
Single test case
First line of input contains two integers n and k, separated by a space and satisfying k ≤ n. The next n lines contain n integers each denoting the colours of subsequent square millimetres of the painting.
Bounds
Common: 1 ≤ n ≤ 800, colours are natural numbers from 1 to 106.
Basic: 1 ≤ k ≤ 50.
Professional: 1 ≤ k ≤ n.
Output
The output for every test case should contain n-k+1 rows with n-k+1 space-separated numbers in every row. The number in row i and column j should represent the number of distinct colours in the fragment beginning with the square millimeter i x j. (The upper left corner of the painting has coordinates 1 x 1.)
Sample input
1 3 2 1 1 2 1 1 2 2 2 3
Sample output
1 2 2 3
Added by: | gawry |
Date: | 2011-10-07 |
Time limit: | 1s-4.630s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |