이미지 정사각형 길이

미르코는 컴퓨터 수업 중 심심해서 그림판을 열고 N x N 픽셀 크기의 이미지를 만들었다.

선생님이 그림판 사용법을 설명할 때 제대로 듣지 않았기 때문에, 미르코는 여러 색의 채워진 정사각형을 그리는 방법만 알고 있다. 그는 먼저 색 1의 정사각형 하나를 그리고, 다음에 색 2의 정사각형 하나를 그리는 식으로 색 K까지 차례대로 그렸다. 나중에 그린 정사각형은 이전에 그린 정사각형의 일부를 덮을 수 있다.

선생님은 완성된 그림을 보고 각 색이 어떤 순서로 그려졌는지는 알아냈지만, 각 정사각형의 처음 변의 길이는 알아내지 못했다.

각 색 A에 대해 가능한 변의 길이는 정수 구간 [a, b]로 나타낼 수 있다. 즉 a <= x <= b인 모든 길이 x에 대해, 최종 이미지가 같아지는 어떤 그리기 과정에서 색 A 정사각형의 변의 길이가 x였을 수 있다.

각 색마다 가능한 변의 길이의 가장 큰 구간을 구하는 프로그램을 작성하라.

첫째 줄에 두 정수 N과 K가 주어진다 (1 <= N <= 1000, 1 <= K <= 9). N은 이미지의 한 변의 길이이고, K는 미르코가 그린 정사각형의 개수이다.

다음 N개 줄에는 길이가 N인 문자열이 하나씩 주어진다. 각 문자는 . 또는 1부터 K까지의 숫자 중 하나이다. .은 어떤 정사각형도 그 픽셀을 덮지 않았다는 뜻이다. 숫자 x는 그 픽셀을 마지막으로 덮은 정사각형의 색이 x였다는 뜻이다.

K개의 줄을 출력한다. i번째 줄에는 두 정수를 출력한다. 이 두 정수는 색 i 정사각형의 가능한 변의 길이의 최솟값과 최댓값을 뜻한다.