“I will never paint again,” Dunno answered. “I paint
and paint, and nobody is ever thankful. Everybody keeps scolding
The great abstractionist artist Herman Brooks invented a new style in
painting—bactorgaphy. Of course, you want to know what kind of a style it
is. That's simple: every painting is live, quite literally. Herman paints with
Such a painting is a real work of art. It's a sight worth seeing—the
fascinating canvas plays with two or three hundred different shades. But how
could this wonder be shown to the people? Photography or video just can't
convey the entire range of colors, and Herman still doesn't have a museum
(modern art custodians don't like innovative ideas, and there's no point
arguing with them). In addition, the painting can be seen in detail only under
a microscope. Finally, it was decided to make several thousand copies of the
best paintings and sell them as souvenirs. However, there is a problem. Herman,
as a real creator, doesn't want to make copies himself, and the hired
bioengineers unanimously claim that a copy can only be made if the exact
sequence of populating the canvas with bacteria is known. Your task is to
restore this sequence.
To help you fulfill the task, the bioengineers provided you with the
- A finished painting is a rectangular canvas divided into equal square
cells with bacteria.
- Before the process of painting is started, the canvas is thoroughly
disinfected. All its cells are empty and contain no bacteria.
- In each cell of the canvas there can be at most four bacteria.
- The painting process consists in settling successively one bacterium
into a free cell of the canvas. When the bioengineers do this, the numbers of
bacteria in the adjacent (top, bottom, left, and right) populated cells increase
by one. If the number of bacteria in a certain cell becomes 5, then 4 of them
die because of overcrowding.
- It is impossible to settle a bacterium into a cell that is already
populated, because it leads to an unpredictable reaction that can damage the
The first line contains the dimensions of the canvas
n and m (1 ≤ n, m ≤ 20).
The description of the painting follows in the form of the table with
n lines containing m integers each. In every cell of this
table the number of bacteria in the corresponding cell of the painting is
written. These numbers range from 1 to 4.
If it is impossible to obtain the described painting by means of the procedure
available to the bioengineers, output “No”. If you managed to find
a sequence that makes it possible to create a copy of Herman's masterpiece,
output “Yes” in the first line, and in the following lines give
this sequence. Each of these lines must contain two integers, which are the
number of line and number of column of the next cell to be populated.
2 2 1
3 1 3
1 2 2
Problem Author: Eugene Krokhalev
Problem Source: NEERC 2008, Eastern subregion quarterfinals