ר

11 http:\olimp.bstu.by
17
9:00 12:00

 
HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Liars and Knights

Section problems

• Sequence
• Bishops
• Polygons
• String manipulations
• Lawyers Council
• Math and Soldiers
• Many-coloured roads
• What about judges?
• Liars and Knights
• Interesting permutations
• Kovrov
• Points
• Roads
• Brackets
• Triangles
• String Multiplication
• Nice Floor

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 3000/4000/4000/4000 ms. Memory limit 65000/80000/80000/80000 Kb.
: , .

NxM people have arrived to the congress of the largest party in Byteland, and they were all seated in N rows, M people in one row. The party consists of two fractions - liars and knights. The representatives of the fraction of knights always speak the truth, and the liars always lie. After the congress, each of the participants said that he had been sitting with the representatives of both fractions at his sides. Two participants are considered to be neighbors, if they are sitting next to each other in one row, or if they occupy the same places in two adjacent rows. The chairman of the party does not know how many there were liars and knights. So he wants to understand with what minimal number of liars such a situation could take place. Your task is to write a program, that will find out the minimal number of liars and the corresponding plan of seating the congress participants.

Input
The first line of the input gives two integers N and M - the number of rows and seats in each row, correspondingly (1 ≤ N ≤ 7, 1 ≤ M ≤ 100).

Output
Write in the first line of the output one number - the minimal quantity of liars in the required seating. The following N lines should show the seating itself, one row in each line. A knight must be shown by the symbol "." (point), and a liar by "x" (small Latin letter x). There should be no other symbols in the lines, not even the spaces. In case you find several ways of seating, show one of them.

Input 1 Output 1
2 3
2
..x
x..
Input 2 Output 2
6 6
10
x...x.
..x...
x....x
...x..
.x...x
x..x..

.

www.contester.ru