COCI '18 Contest 6 #2 Konj

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Domagoj loves drawing horses at leisure. For a long time, he's been a proud member of social groups dealing with this subject. But Domagoj is a very special boy, so because of his drawing technique most people do not understand his masterpieces.

One of his most famous drawings is #define HORSE 42-42, also known as Ordinary Horse.

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

You must be wondering "Where is that horse?" and "Is everything all right with Domagoj?" because you only see some numbers on the drawing. The first question will be answered in the next section, while the answer to the second question also interests the author of this task.

In order to understand the drawing, you need to understand Domagoj's drawing technique. The first number in the drawing is the number N denoting the number of line segments that may have been drawn. Thereafter, the following N lines have four numbers, A_i, B_i, C_i and D_i, which describe the i^{th} line segment extending from the point (A_i, B_i) to the point (C_i, D_i). In the last line of the drawing there are two numbers, X and Y, the coordinates of point T. Domagoj will draw all the line segments that contain the point T and all that are directly or indirectly connected to a line segment that contains point T. For two line segments L_1 and L_2 we say that they are directly connected if they have a common end point, and they are indirectly connected if there is a sequence of line segments L_1, H_1, H_2, \dots, H_k, L_2 such that the line segments L_1 and H_1 are directly connected, H_1 and H_2 are directly connected, …, H_k and L_2 are directly connected.

Your task is to print a rectangular matrix P of characters that displays Domagoj's drawing. The value of P_{a,b} should be set to # if the point with the coordinates (a, b) is part of some line segment drawn, otherwise this value should be set to .. Coordinate a in the matrix rises from left to right, while coordinate b rises from bottom up. Matrix P should contain all points that are part of a drawn line and should not contain any single row or column that contains only characters ., i.e. it should be minimal in size.

Input

In the first line of the input there is a positive integer N (1 \le N \le 200\,000). In the next N lines there four non-negative integers A_i, B_i, C_i and D_i (0 \le A_i, B_i, C_i, D_i \le 300). For each line segment it will hold either A_i \ne C_i or B_i \ne D_i. No two line segments will intersect, but some might have a common end point. All the lines will be parallel to the coordinate axes.

In the last line of the input there will be two non-negative integers X and Y, coordinates of the point T. Point T will be part of at least one of the given line segments.

Output

Print required matrix P from the task.

Scoring

In the test samples totally worth 30% of the points you should draw all line segments.

Sample Input 1

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

Sample Output 1

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

Explanation for Sample Output 1

In the first example all the line segments should be drawn except the last.

Sample Input 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

Sample Output 2

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

Explanation for Sample Output 2

In the second example all the line segments should be drawn to get the drawing of the name "Summarized horse".


Comments

There are no comments at the moment.