|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.
Common: 1 ≤ n ≤ 800, colours are natural numbers from 1 to 106.
Basic: 1 ≤ k ≤ 50.
Professional: 1 ≤ k ≤ n.
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.)
1 3 2 1 1 2 1 1 2 2 2 3
1 2 2 3
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM64|