Problem description

Wiktor walczy z zadaniem Zamek z XXIV Olimpiady Informatycznej. Zadanie ma już prawie rozwiązane, ale niestety, nie działa na niektórych przygotowanych przez niego testach. Wiktor mógłby łatwiej zdebugować program, gdyby przygotowane przez niego testy mógł wyświetlić w terminalu.

Mapa zamku naniesiona jest na układ współrzędnych i mieści się w całości w prostokącie, którego lewy dolny róg znajduje się w punkcie (0,0), a prawy górny róg w (w,h). Zamek dzieli się na komnaty, które w całości wypełniają zamek. Jedna z komnat jest komnatą początkową, a jedna końcową. Niektóre z komnat mogą być zablokowane. Napisz kod, który wczyta opis zamku i narysuje go jako ASCII-art na ekranie!

Wejście

W pierwszym wierszu standardowego wejścia znajdują się cztery liczby naturalne w, h, N i M, oznaczające odpowiednio wymiar mapy, liczbę komnat zamku oraz liczbę blokad. W drugim wierszu znajduje się para liczb x_p, y_p oznaczające współrzędne punktu początkowego. W trzecim wierszu znajdują się liczby x_s, y_s oznaczające współrzędne punktu końcowego. Obie pary współrzędnych znajdują się wewnątrz pewnej komnaty (a nie na brzegu).

W następnych N wierszach znajdują się opisy komnat, i-ty z nich zawiera cztery liczby całkowite x₁, y₁, x₂, y₂ oznaczające, że prostokąt odpowiadający i-tej komnacie ma przeciwległe wierzchołki w punktach (x₁,y₁) oraz (x₂,y₂).

W następnych M wierszach znajdują się opisy blokad. i-ty z nich składa się z dwóch liczb całkowitych x, y oznaczających, że komnata zawierająca punkt (x,y) jest zablokowana.

Wyjście

Na wyjściu należy narysować ASCII-art odpowiadający mapie zamku. Ze względu na to, że wszystkie znaki mają tę samą szerokość i wysokość, należy myśleć, że osie pionowe i poziome układu współrzędnych (tj. wszystkie proste pionowe i poziomie przechodzące przez punkty kratowe) mają tę samą szerokość i wysokość, co kwadraty 1 × 1 pomiędzy nimi. Zatem pierwsze pole pierwszego wiersza wyjścia reprezentuje punkt (0,h), a pole o rogach w (0,h) oraz (1,h−1) reprezentuje drugi znak drugiego wiersza. Rogi wszystkich komnat powinny zostać oznaczone znakiem +. Pionowe ściany komnat powinny zostać narysowane przy użyciu znaków |, poziomie przy pomocy -. Punkt początkowy powinien zostać oznaczony przy pomocy pojedynczego znaku P. Punkt końcowy powinien zostać oznaczony przy pomocy pojedynczego znaku S. Zablokowane komnaty powinny zostać w całości wypełnione znakami X. W innym razie powinny być wypełnione znakami spacji. Dla rozjaśnienia zalecane jest zapoznanie się z testem przykładowym.

Ograniczenia

1 ≤ w, h ≤ 2000, 1 ≤ N, M ≤ 1 000 000, wszystkie współrzędne x, y spełniają nierówności 0 ≤ x ≤ w, 0 ≤ y ≤ h.

W testach wartych 50% punktacji zachodzi dodatkowy warunek M = 0 (tzn. nie występują żadne blokady).

Przykład

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

+-----+---+---+
|     |   |   |
|     +---+   |
|     |XXX|   |
|     |XXX| S |
|     |XXX|   |
|     +---+-+-+
|     |XXXXX| |
+-----+XXXXX| |
|     |XXXXX| |
| P   +---+-+-+
|     |   |   |
+-----+---+---+

5 5 4 0
1 1
4 4
0 0 3 3
0 3 3 5
3 0 5 2
3 2 5 5

+-----+---+
|     |   |
|     | S |
|     |   |
+-----+   |
|     |   |
|     +---+
|     |   |
| P   |   |
|     |   |
+-----+---+