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.
Input
The only input line contains the integers n and
m (1 ≤ n, m ≤ 10; the product nm
is even).
Output
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.
Samples
input | output |
---|
4 4
| 2
1100
0110
0000
0000
|
2 5
| 2
11110
00000
|
Problem Author: Sergey Pupyrev
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008