题目描述

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 $w_x$ and $w_y$ 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 \leq d_x, d_y \leq 10^3$) are the maximum dimensions of the crystal structure, and $k (1 \leq k \leq 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 \leq w_x \leq d_x$ and $-d_y \leq w_y \leq d_y$, but not both zero) denoting the direction of the wind. Then comes an integer $b$ ($0 \leq b \leq 10^5$) giving the number of boundaries encountered by this wind. The line finishes with $b$ distinct pairs of integers $x,y$ ($1 \leq x \leq d_x$ and $1 \leq y \leq 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.

题目大意

题目描述

你是一个科学团队中的一员，正在开发一种在分子级别上成像晶体结构的新技术。这种技术涉及在晶体表面吹送一股非常微弱的风，并以不同的角度吹送，以便检测边界（通过暴露给风的分子来表示）。这个过程会重复进行，每个吹送方向的边界都会被记录下来。你的团队已经收集到了数据，但是如同大多数应用科学一样，现在真正的工作，即分析工作必须开始。

对于给定的晶体，你将接收到风以不同方向吹送过晶体表面的数据，以及每个风吹过时遇到的所有边界的位置。对于在方向（$w_x, w_y$）吹送的风，边界被定义为位置（$x, y$），使得一个分子位于（$x, y$），并且没有分子位于（$x-w_x, y-w_y$）。请注意，出于技术原因，$w_x$ 和 $w_y$ 不一定互质。

这些数据可能无法唯一确定晶体的结构。你必须找到两个与观测数据一致且分子数最少和最多的晶体结构。

例如，在第一个示例输入中，通过给定的风，出现了9个不同的分子。必须有一个在位置（$3, 3$）处的分子，否则（$4, 2$）将成为第三股风的边界。出于类似的原因，必须在位置（$4, 4$）和（$5, 5$）处有分子。不能再有其他分子，因为它们会导致一些风的附加观测结果。

输入格式

输入的第一行包含三个整数 $d_x$、$d_y$ 和 $k$，其中 $d_x$ 和 $d_y$（$1 \leq d_x, d_y \leq 10^3$）是晶体结构的最大尺寸，$k$（$1 \leq k \leq 10$）是风吹过晶体的次数。

接下来的 $k$ 行中，每一行都描述了一次吹风的数据。第一对整数 $w_x$ 和 $w_y$（$-d_x \leq w_x \leq d_x$，$-d_y \leq w_y \leq d_y$，但不能同时为零）表示风的方向。然后是一个整数 $b$（$0 \leq b \leq 10^5$），表示这股风遇到的边界数量。接下来的 $b$ 对不同的整数 $x$、$y$（$1 \leq x \leq d_x$，$1 \leq y \leq d_y$）表示每个观测到的边界。

你可以假设输入数据与至少一个晶体是一致的，并且没有分子存在于指定尺寸范围之外。

输出格式

输出两个晶体结构的文本表示，两个结构之间用一个空行分隔。每个结构有 $d_y$ 行，每行有 $d_x$ 个字符，左上角对应位置（$1, 1$）。第一个结构是与观测结果一致的包含最少分子数量的结构，第二个结构是包含最多分子数量的结构。使用 '#' 表示分子存在的位置，使用 '.' 表示分子不存在的位置。

6 6 3
1 1 3 3 1 1 3 2 2
0 2 6 3 1 1 3 2 2 6 4 5 3 4 2
1 -1 4 1 3 2 4 3 5 4 6

..#...
.#.#..
#.#.#.
.#.#.#
..#.#.
...#..

..#...
.#.#..
#.#.#.
.#.#.#
..#.#.
...#..

5 4 2
1 0 6 1 1 4 1 2 2 5 2 2 3 3 4
0 -1 7 1 1 4 1 5 2 2 3 3 4 4 4 5 4

#..#.
.#..#
.#...
..###

##.##
.##.#
.###.
..###