Description

Domagoj has a strange way of drawing. First, he prepared $N$ line segments to be drawn. Each segment connects two points, namely $(A_i,B_i)$ and $(C_i,D_i)$. Then, he chooses a point $T$. After that, Domagoj will draw all segments that satisfy at least one of the following conditions:

• They pass through point $T$.
• They are directly or indirectly connected to a segment that passes through point $T$.

We say that two segments $L_1, L_2$ are directly connected if they share an endpoint. We say that $L_1, L_2$ are indirectly connected if $L_1$ is directly connected to $H_1$, $H_1$ is directly connected to $H_2$, $\cdots$, and $H_k$ is directly connected to $L_2$.

Your task is to print the final drawing made by Domagoj. The output should be in the form of a matrix $P$. If there is a segment passing through $(a,b)$, output # at position $P(a,b)$; otherwise, output the character .. Note that the horizontal coordinate $a$ increases from left to right, and the vertical coordinate $b$ increases from bottom to top (consistent with the Cartesian coordinate system). The matrix $P$ must not contain any row or column consisting entirely of . characters. That is, while containing all segments that need to be drawn, the matrix must be the smallest possible in size.

Input Format

The first line contains the number of segments to be drawn, $N$.

The next $N$ lines each contain four non-negative integers $A_i, B_i, C_i, D_i$, representing the endpoints $(A_i,B_i)$ and $(C_i,D_i)$ of the $i$-th segment. For each segment, exactly one of $A_i \neq C_i$ and $B_i \neq D_i$ holds. In other words, every segment is parallel to one of the coordinate axes. Also, no segments intersect, but they may share endpoints.

The next line (the last line) contains integers $X, Y$, representing the coordinates of $T$. It is guaranteed that at least one segment passes through point $T$.

Output Format

Output the required matrix $P$.

15
2 2 6 2
2 2 2 6
6 2 6 4
6 4 6 6
2 6 6 6
6 2 8 2
8 2 10 2
10 2 12 2
12 2 12 4
12 4 6 4
6 2 6 1
8 2 8 0
10 2 10 1
12 2 12 0
42 42 42 43
2 2

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

6
1 1 10 1
10 1 10 3
10 3 1 3
1 3 1 1
10 3 11 3
11 3 11 6
2 1

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

Hint

Explanation for Sample 1

All segments except the last one need to be drawn. That is, except for the segment connecting $(42,42)$ and $(42,43)$, all others must be drawn.

Explanation for Sample 2

All segments must be drawn.

Constraints

For $30\%$ of the testdata, all segments need to be drawn.

For $100\%$ of the testdata, $1 \le N \le 2 \times 10^5$, $0 \le A_i, B_i, C_i, D_i \le 300$.

Notes

The score for this problem follows the original COCI setting, with a full score of $70$.

Translated from COCI2018-2019 CONTEST #6 T2 Konj.

Translated by ChatGPT 5