Image Square Lengths

Mirko was bored during computer class, so he opened Paint and created an N x N pixel image.

Because he had not paid attention while the teacher explained the tool, Mirko only knows how to draw filled squares in different colors. He first drew one square of color 1, then one square of color 2, and so on through color K. A later square may cover part of an earlier square.

After the teacher noticed the drawing, she could reconstruct the order in which the colors were drawn, but not the original side lengths of the squares.

For each color A, the possible side lengths form an integer interval [a, b]: every length x with a <= x <= b could have been the side length of the square of color A in some drawing that produces the final image.

Write a program that finds this largest interval for every color.

The first line contains two integers N and K (1 <= N <= 1000, 1 <= K <= 9): the side length of the image and the number of squares Mirko drew.

Each of the next N lines contains N characters. Each character is either . or one of the digits from 1 to K. A . means no square ever covered that pixel. A digit x means the last square to cover that pixel had color x.

Print K lines. On line i, print two integers: the smallest and largest possible side length of the square of color i.