ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Tram Tile

Time limit: 0.5 second
Memory limit: 64 MB
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1609. Tram Tile