Practice Coding with the exercise "Shikaku Solver"

Statement

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 Width and Height 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

Solve it

A higher resolution is required to access the IDE