직사각형 격자의 각 칸에는 0, 1, 2 중 하나가 적혀 있다. 0이 적힌 칸은 이동할 수 없고, 1이 적힌 칸은 이동할 수 있다. 2가 적힌 칸은 시작 칸이며, 시작 칸도 이동할 수 있다.

한 번 이동할 때 상하좌우로 인접한 칸으로 이동할 수 있다. 시작 칸에서 격자의 각 칸까지의 최단 거리를 구해 보자.

입력

첫째 줄에 격자의 세로 크기 \(H\)와 가로 크기 \(W\)가 공백으로 구분되어 주어진다.

다음 \(H\)개의 줄에 각 칸의 값이 공백으로 구분되어 주어진다.

출력

\(H\)개의 줄에 각 칸에 대한 결과를 입력과 같은 형태로 출력한다.

• 시작 칸에는 0을 출력한다.
• 이동할 수 없는 칸에는 0을 출력한다.
• 시작 칸에서 도달할 수 있는 칸에는 최단 거리를 출력한다.
• 이동할 수 있지만 시작 칸에서 도달할 수 없는 칸에는 -1을 출력한다.

각 줄의 수는 공백으로 구분한다.

제한

• \(1 \le H,W\)
• \(H \times W \le 1,000\)
• 값이 2인 칸은 정확히 하나 존재한다.

예제 입력 1

4 5
1 1 0 1 1
1 2 1 0 1
0 1 1 0 1
1 1 0 1 1

예제 출력 1

2 1 0 -1 -1
1 0 1 0 -1
0 1 2 0 -1
3 2 0 -1 -1