포스텍 학생들이 바라 마지않아 왔던 프로그래밍 대회 전용 경기장, POSTECH Programming Colosseum이 완공을 앞두고 도색만을 기다리고 있다.

경기장은 $N$행 $M$열으로 배치된 $N \times M$개의 방으로 이루어져 있다. POSTECH Programming Colosseum의 관리자 포닉스는 원활한 대회 관리를 위해 다음 조건을 만족하도록 각 방에 칠할 색을 정하려 한다.

• 각 방은 정확히 $1$개의 색으로 칠해져야 한다.
• 쾌적한 대회 진행을 위해, 같은 색으로 칠해진 방들은 모두 연결되어 있어야 한다. 구체적으로는 색 $C$로 칠해진 서로 다른 두 방 $A$와 $B$에 대해 $A$에서 출발해 상하좌우로 인접한 방들 중 색 $C$로 칠해진 방으로 이동하는 것을 반복해 $B$에 도달할 수 있어야 한다.
• 효율적인 인원 통제를 위해, 같은 색으로 칠해진 서로 다른 두 방에 대해, 같은 색으로 칠해진 방들만 지나 둘을 잇는 경로는 유일해야 한다.

즉, 같은 색으로 칠해진 방들은 트리 구조를 이뤄야 한다.

포닉스는 경기장이 혼잡해지는 것을 막기 위해 가능한 적은 종류의 색을 사용해 경기장을 칠하려 한다. 포닉스를 도와 POSTECH Programming Colosseum을 완성시켜 보자.

입력 형식

첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 2000$)

출력 형식

첫째 줄에 사용해야 하는 색의 종류의 최솟값 $K$를 출력한다.

둘째 줄부터 $N$줄에 걸쳐 각 줄에 $M$개의 정수를 공백으로 구분해 출력한다.

$i+1$번째 줄의 $j$번째 정수는 경기장의 $i$번째 행의 $j$번째에 위치한 방에 칠해질 색을 의미한다. 이 정수들은 모두 $1$ 이상 $K$ 이하여야 한다.

예제

예제 1

입력

5 5

출력

2
1 1 1 1 1
2 2 2 2 1
1 1 1 2 1
1 2 2 2 1
1 1 1 1 1

예제 2

입력

1 3

출력

1
1 1 1 

노트

왼쪽의 세 도색은 모든 조건을 만족하는 경우이다. 오른쪽의 세 도색은 왼쪽의 예시부터 각각 $2$번째 조건, $3$번째 조건, 그리고 가능한 적은 종류의 색을 사용해야 한다는 조건을 만족하지 않는 경우이다.