An urgent problem is the seating of spectators in the auditorium of a theater, cinema, concert hall, etc. respecting the distance between the occupied places. At the same time, it is desirable to seat as many spectators as possible in the hall, observing the minimum required distance between seats.
The auditorium is a
NxM rectangle consisting of single squares of seats. The distance between places is the sum of the distances between them horizontally and vertically. The distance between places horizontally and vertically is the modulo difference of their coordinates, assuming that the distance between two adjacent places horizontally and vertically equals 1.
For example, the figure below shows an auditorium measuring
3x4, in which the audience sits on three seats
A,
B and
C.
Distance between places A and B is 3 (2 vertically plus 1 horizontally), distance between places B and C< /code> is 3 (0 vertically plus 3 horizontally), the distance between A and C is 4 (2 vertically plus 2 horizontally).
You are given the dimensions of the auditorium NxM and the minimum distance between spectators d. You need to place as many spectators as possible in a room of size NxM so that the distance between any two occupied seats is at least d.
The answer must be written as N lines, each line contains M characters equal to 0 or 1. < code>0 indicates free space, 1 indicates occupied space.
For example, in a hall of size 3x4, a maximum of 3 people can be accommodated at a distance of at least 3.
An example of such a placement is shown in the figure above, and the answer in this case is written as follows:
0100
0000
1001
You need to answer several options for the task: 3-1, 3-2, 3-3, 3-4.
In task 3-1 N = 3, M = 5, d = 2.
In task 3-2 N = 6, M = 10, d = 4.
In task 3-3 N = 4, M = 6, d = 3.
In task 3-4 N = 7, M = 10, d = 3.