Задача E. Соединительная линия ≡

Условие

На плоскости, разделённой на клетки, заданы два прямоугольника с координатами (x₁, y₁)−(u₁, v₁), (x₂, y₂)−(u₂, v₂) и две различные точки с координатами (x_s, y_s) и (x_d, y_d). Требуется:

1. найти кратчайший путь между указанными точками, переходящий от клетки к клетке по вертикали или горизонтали и не пересекающий прямоугольники;
2. вывести изображение прямоугольников и кратчайшего пути.

При этом пустая клетка должна изображаться символом '.', клетка, принадлежащая прямоугольнику — символом '#', начальная и конечная точки — символом '*', клетка, через которую путь проходит по горизонтали — символом '-', клетка, через которую путь проходит по вертикали — символом '|', клетка, в которой путь делает поворот — символом '+'.

Изображение должно быть прямоугольником минимального размера, достаточного, чтобы вместить все непустые клетки. Ось ординат должна быть направлена снизу вверх.

Формат входного файла

Во входном файле содержатся целые числа x₁ y₁ u₁ v₁ x₂ y₂ u₂ v₂ x_s y_s x_d y_d.

Формат выходного файла

В выходном файле должно содержаться изображение, выведенное построчно. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ x_i, y_i, u_i, v_i ≤ 100,

Прямоугольники могут пересекаться. Начальная и конечная точки не лежат внутри прямоугольников.

Примеры тестов

2 3 7 5  6 7 8 8  6 2  5 9

...*...
...|###
...|###
...+--+
######|
######|
######|
....*-+

2 3 7 6  8 7 6 8  6 2  5 9

...*---+
....###|
....###|
######++
######|.
######|.
######|.
....*-+.