E. Pipes#8755
Cossack Vus aspired to become the president of Potokolandia. To achieve this, he needed to perform a good deed for the citizens, thereby enhancing his popularity. He chose to repair the country's water supply system. This system is underground and is divided into equal square sections, forming a grid of n \times m.
The sections are numbered from top to bottom, from to , and from left to right, from to . Each section can either be empty (represented by the symbol ) or contain one of types of pipes:
The water supply system is considered closed if every pipe's ends are connected to the ends of other pipes.
Recently, you were appointed as Cossack Vus's deputy for water supply issues. You have the ability to rotate any pipe by angles that are multiples of 90^\circ. Your task is to make the water supply system closed through rotations or to determine if it is impossible.
The first line contains three integers , , and (1 \le n, m \le 400, 0 \le g \le 8) — the dimensions of the grid and the group number, respectively.
Each of the following lines contains integers a_{i,j} (0 \le a_{i,j} \le 6), indicating the type of pipe located in the cell with coordinates (, ).
Print NO if it is impossible to rotate the pipes to form a closed system. Otherwise, print YES, followed by lines with numbers each, describing the closed system formed by the rotations, in the format described above.
Example 1
Example 2
Example 3
Illustration for test examples: initial and closed state (if it exists):
(7 points) 1 \le n, m \le 3;
(9 points) 1 \le n, m \le 400; up to 4 corner pipes;
(12 points) 1 \le n, m \le 400; up to 8 corner pipes;
(13 points) 1 \le n \le 400, m = 2;
(13 points) 1 \le n, m \le 400; if a solution exists, then in at least one answer, each closed loop consists of 4 corner pipes and any number of straight pipes;
(14 points) 1 \le n \le 400, m = 4;
(15 points) 1 \le n, m \le 50;
(17 points) without additional restrictions.