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

NEERC 2008, Eastern subregion quarterfinals

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Abstractionism to the People

Time limit: 1.0 second
Memory limit: 64 MB
“I will never paint again,” Dunno answered. “I paint and paint, and nobody is ever thankful. Everybody keeps scolding me.”
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 bacteria.
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 following information.
  • 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 whole painting.


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.


3 3
2 2 1
3 1 3
1 2 2
2 2
2 1
1 1
1 2
2 3
1 3
3 3
3 2
3 1
Problem Author: Eugene Krokhalev
Problem Source: NEERC 2008, Eastern subregion quarterfinals
To submit the solution for this problem go to the Problem set: 1649. Abstractionism to the People