A higher resolution is required to access the IDE

- 71

## 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 (

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 (

Constraints

10 ≤

`W`,`H`≤ 30Example

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

A higher resolution is required to access the IDE