$N$행 $M$열 격자판의 각 격자가 흰색 또는 검은색으로 칠해져있다. 각 칸에 대해 다음의 3가지중 1가지 행동을 취할 수 있다.

1. 아무 변화도 주지 않는다.
2. 선택한 칸과 인접한 모든 칸의 색을 반전시킨다 (선택한 칸은 반전시키지 않는다).
3. 선택한 칸 및 그 칸과 인접한 모든 칸의 색을 반전시킨다.

당신은 모든 칸을 흰색으로 만들고자 한다. 모든 칸을 흰색으로 만드는 방법을 구하여라.

Input

첫 줄에 $N$과 $M$이 주어진다. ($ 1 \le N, M \le 2000$) 다음 줄부터 $N$개의 줄에 걸쳐 각 줄에 길이 $M$의 문자열이 주어진다. 문자열은 'B'와 'W'로 이루어져 있으며, 각각 검은색 및 흰색 칸을 의미한다.

Output

만약 모든 칸을 흰색으로 만드는 것이 불가능하다면 첫 줄에 -1을 출력한다. 가능하다면 첫 줄에 1을 출력하고, 다음 줄부터 $N$개의 줄에 걸쳐 $M$개의 수를 공백 없이 출력한다. $i$번째 줄의 $j$번째 수는 $i$번째 줄, $j$번째 칸에 취한 행동을 나타낸다. 1은 아무런 변화를 주지 않은 것, 2는 인접한 모든 칸을 반전시킨 것, 3은 그 칸 및 인접한 모든 칸을 반전시킨 것을 의미한다.

Examples

Input 1

2 3
WBW
BWB

Output 1

1
111
121

Input 2

1 1
B

Output 2

1
3