The Caponians, an alien strain coming from an unspecified planet in

the galaxy, have been planning for quite a while the invasion of the

planet Earth. To do this, they have created and installed in various

points of the planet "mind bending machines". This machinery reduces

the intelligence of humans through the telephone network $[1].$

Once the phase of reducing human intelligence is over, the next

step towards the conquest of the Earth will be the landing on our

planet, which will happen as soon as the Caponians will find some

areas where they can land with their spaceships.

A spaceship $($seen from above$)$ can be represented as a rectangle of

dimensions W $($width$)$ and H $($height$).$ When considering the necessary

space for landing, a spaceship will open hatches on the $4$ sides of

the rectangle. These gates are one per side.

The areas protrude by the same amount D$,$ in order to allow to open on

each side a landing hatch. Each hatch is therefore as wide as the side

of the spaceship on which it is located and long as D$,$ whatever side

it is on$.$

The Caponians would like to land with their spaceships in some of our

cities by looking at the city map. A city can be represented as a black

rectangular image, in which every building is represented as a colored

rectangle $($each building has a color that uniquely identifies it$).$

In order to define the final details of the landing plan, the Caponians

need an algorithm which, given a map of a city and a

list of spaceships, confirms or not if

each spaceship has enough space to land in that city.

To land, a spaceship has to open its $4$ hatches. Spaceships do not land

in the city at the same time, so they must be evaluated separately

from each other.

$(1)$ So$,$ given a black image $($city$)$ filled with solid colored

rectangles $($buildings$),$ where each building has its own unique color,

it is necessary:

$-$ determine position, size and color of each rectangle

$-$ save in a text file one rectangle per line

$-$ in the file, each rectangle is represented with a sequence of $7$ values:

x$,$ y$,$ w$,$ h$,$ r$,$ g$,$ b

separated by commas, in order of decreasing y$-$coordinate $($the row

nunber$).$ In case of equal y$,$ in order of increasing x $($row$-$pixel number$).$

$(2)$ Next, we are given a text file containing N triple of

integers. Each triple is separated internally and from the other

triples by a variable number of spaces, tabs or carriage returns. Each

triple represents width W$,$ height H and minimum distance D $($see below$)$

of a spaceship that you would like to land in a city at step $(1)$:

$-$ So we have to return a list of N Boolean values: the i$-$th value in

the list is True if there is enough space in the image to

insert the i$-$th spaceship.

$-$ a rectangle can be inserted in the image if there exists at least

one position in the image where there is enough space $($i$.$e$.,$ an area

consisting entirely of black pixels$)$ to hold the i$-$th spaceship.

A spaceship can land if contains the rectangle itself, plus the $4$

"extensions" of the rectangle, i$.$e$.$ the $4$ hatches of the spaceship.

For example, if a spaceship has $2$ pixels of width and $3$ of height and

D $=2,$ we will have to look for an area in the image to contain the

following figure:

$**$

$**$

$*++*$

$*++*$

$*++*$

$**$

$**$

where the $+$ symbols are the pixels of the $2$x$3$ rectangle$/$spaceship and the $*$

are the pixels of the $4$ extensions$/$hatches$.$

Example:

Given the following image represented with one character for each

pixel, where $"."$ is a black pixel and characters other than $"."$ are

colored pixels $(*=$red, $+=$green$)$:

$**....$

$**....$

$......$

$......$

$....++$

$....++$

The file with the found rectangles must contain the lines:

$4,4,2,2,0,255,0$

$0,0,2,2,255,0,0$

and given the following spaceships:

$(3,3,0)$

$(2,2,4)$

$(1,1,3)$

$(4,2,1)$

$(2,4,1)$

the returned list will be: $[$True$,$ False, False, False, False$].$

In fact only the first spaceship can land for example in the zone marked by

$\text{'}$X$\text{'}($it has no doors, in fact D $=0)$

$**.$XXX

$**.$XXX

$...$XXX

$......$

$....++$

$....++$

while the others don't enter in the map because, even if they have a point

in which they can land, they cannot open all the hatches.