Public transportation is burgeoning in Yekaterinburg. The municipal authorities have imminent plans to repair about 20 kilometers of tram lines using a new technology involving specially-designed bricks. Implementation of the new method of repairing pavement between rails started last summer, and the first results can already be seen.

For example, Ravshan and Dzhamshud's brigade has paved with new bricks almost two crossroads in the city center. This amazing work speed is explained by a trick used by their master. Before the start of repair work, he arranges several bricks between rails in such a way that there is only one way to continue the paving. As a result, the time is saved that is usually spent for designing brick arrangements, for which other brigades spend the most part of their workdays.

Each brick has size 1 × 2. It is required to pave with bricks a rectangular domain of size n × m. Determine the minimal number of bricks the master should arrange so that the final arrangement (i.e., a complete pavement of the rectangle) is determined uniquely. Two arrangements are considered equal if all positions of all their bricks coincide.

The only input line contains the integers n and m (1 ≤ n, m ≤ 10; the product nm is even).

In the first line, output the minimal number of bricks the master should arrange. The following n lines contain m symbols each and describe one of the possible initial arrangements. The symbol “1” denotes a cell occupied by a brick, and the symbol “0” denotes an empty cell.