## Goal

**Find all solutions to a Shikaku puzzle.**

Shikaku is a puzzle played on a rectangular grid. Some of the squares in the grid are numbered. The objective is to divide the grid into rectangular pieces such that each piece contains exactly one number, and that number represents the area of the rectangle.

If the puzzle is poorly designed, there might be more than one solution. The goal here is to find all the solutions to a given puzzle.

We will use the letters (A-Z,a-z) to represent the rectangles. Going left to right then top to bottom, you should encounter the rectangles (A-Z,a-z) in order.

https://en.wikipedia.org/wiki/Shikaku
Input

**Line 1:** The `W`idth and `H`eight of the puzzle, space separated.

**Next **`H` lines: `W` space separated numbers to fill out the grid (0 for blank cells, otherwise the area value).

Output

**Line 1:** The number of solutions to the puzzle. There will always be at least one solution.

**Next **`H` lines: `W` characters (A-Z,a-z) for each line of the solution. If there is more than one solution, return the solution that comes first if you concatenate all rows and sort lexicographically.

Constraints

10 ≤ `W`,`H` ≤ 30

Example

Input

10 10
0 0 0 0 0 0 0 0 9 0
0 0 0 0 0 0 9 0 0 0
0 0 0 0 0 0 0 0 0 0
0 20 0 0 8 0 0 0 6 0
0 0 0 0 0 0 0 0 0 0
0 0 0 6 0 0 6 0 0 0
10 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 6 0 6 0 0 0 8 0
0 0 0 0 0 0 6 0 0 0

Output

1
AAAABBBCCC
AAAABBBCCC
AAAABBBCCC
AAAADDDDEE
AAAADDDDEE
FFGGGHHHEE
FFGGGHHHII
FFJJKKLLII
FFJJKKLLII
FFJJKKLLII