Humanity's Last Code Exam / 2021_A / Crystal Crosswind

## Problem Statement

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.

### Input

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

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.

### Sample Input 1

## Problem Statement

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.

### Input

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

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.

### Sample Input 1