26130번 - Crystal Crosswind 다국어

You are part of a scientific team developing a new technique to image crystal structures at the molecular level. The technique involves blowing a very fine wind over the surface of the crystal at various angles to detect boundaries (indicated by molecules that are exposed to the wind). This is repeated with different wind directions and the boundaries observed for each direction are recorded. Your team has already collected the data, but – as is often the case with applied science – now the real work, analysis, must begin.

For a given crystal, you will receive the directions in which wind blew over the surface, and the locations of all boundaries encountered by each of these winds. For a wind blowing in direction (w_x, w_y), a boundary is defined as a location (x, y) such that a molecule exists at (x, y) and no molecule exists at (x − w_x, y − w_y). Note that for technical reasons wx and wy are not necessarily relatively prime.

The data might not uniquely determine the structure of the crystal. You must find the two unique structures with the minimal and maximal number of molecules consistent with the observations.

For example, in the first sample input, nine different molecules are directly encountered by the given winds. There must be a molecule at location (3, 3) because otherwise (4, 2) would be a boundary for the third wind. For similar reasons, there must be molecules at (4, 4) and (5, 5). There cannot be any further molecules as they would result in additional observations for some of the winds.

The first line of input contains three integers d_x, d_y, and k, where d_x and d_y (1 ≤ d_x, d_y ≤ 10³) are the maximum dimensions of the crystal structure, and k (1 ≤ k ≤ 10) is the number of times wind was blown over the crystal.

Each of the remaining k lines specifies the data for one wind. These lines each start with two integers w_x and w_y (-d_x ≤ w_x ≤ d_x and -d_y ≤ w_y ≤ d_y, but not both zero) denoting the direction of the wind. Then comes an integer b (0 ≤ b ≤ 10⁵) giving the number of boundaries encountered by this wind. The line finishes with b distinct pairs of integers x, y (1 ≤ x ≤ d_x and 1 ≤ y ≤ d_y) listing each observed boundary.

You may assume the input is consistent with at least one crystal and that no molecules exist outside the specified dimensions.

Output two textual representations of the crystal structure separated by an empty line. Each structure has d_y rows of d_x characters, with the top-left corner corresponding to location (1, 1). The first is the structure with the minimal number of molecules consistent with the observations, the second is the maximal one. Use ‘#’ for a location where a molecule exists and ‘.’ for a location where no molecule exists.