내륙국

캐나다는 내륙국이 아니다. 캐나다는 바다와 맞닿아 있고, 실제로 세 대양과 접한다.

세계에는 볼리비아와 몽골을 포함해 내륙국이 46개 있다. 내륙국은 바다와 맞닿아 있지 않지만, 다른 나라 하나만 지나면 바다에 닿는 나라다. 예를 들어 몽골에 있는 사람은 러시아를 지나 바다에 닿는다.

리히텐슈타인과 우즈베키스탄은 세계에서 유일한 이중 내륙국이다. 두 나라는 내륙국이면서, 두 나라를 둘러싼 나라도 모두 내륙국이다. 그래서 우즈베키스탄을 떠나 바다에 닿으려면 서로 다른 나라를 적어도 둘 지나야 한다.

지도가 주어지면 각 나라가 얼마나 내륙에 있는지 구하라. 어떤 나라의 칸 하나라도 가로, 세로, 대각선으로 인접한 칸에 물이 있으면 그 나라는 내륙국이 아니고, 그 나라의 값은 $0$이다. 내륙국이면 그 나라에서 물까지 가는 데 넘어야 하는 국경의 최소 개수가 값이다. 이동은 가로, 세로, 대각선으로 인접한 칸으로 한 칸씩 한다. 국경을 넘는다는 것은 어떤 나라의 칸에서 다른 나라의 칸으로 한 칸 이동하는 것이다. 물이 있는 칸은 나라가 아니므로, 물로 들어가는 이동은 국경을 넘는 것으로 세지 않는다.

한 나라가 섬처럼 여러 조각으로 나뉘어 있을 수도 있다. 이때 그 나라의 값은 각 조각에서 구한 값 중 최솟값이다.

첫째 줄에 $N$과 $M$이 주어진다. ($1 \le N, M \le 1000$)

다음 $N$개의 줄에는 대문자 $M$개가 공백 없이 주어진다. 각 나라는 서로 다른 대문자 하나로 나타낸다. 글자 W는 나라 이름으로 쓰지 않고 바다나 호수의 물을 나타낸다. 지도에는 물이 있는 칸이 적어도 하나 있다.

지도에 나오는 나라마다 한 줄씩, 그 나라를 나타내는 글자와 그 나라의 값을 공백 하나로 구분해 출력한다. 나라는 알파벳 순서로 출력한다.