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 10^{6}.

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 |