C. Labirint

Sizga \(W \times H\) o'lchamdagi (kengligi \(W\) ta katak, balandligi \(H\) ta katak) matnli ASCII formatda berilgan labirint taqdim etiladi. Labirintda kirishdan chiqishgacha bo'lgan aniq bitta yagona to'g'ri yo'l mavjud.

• Har bir katak matnda maxsus ASCII simvollar yordamida chiziladi. Labirintning umumiy satrlar soni \(2\times H + 1\) tani, har bir satrdagi belgilar soni (kengligi) esa \(4\times W + 1\) tani tashkil qiladi. Devorlar \(+\), \(-\) va \(|\) simvollari orqali, yo'laklar esa bo'sh joylar yordamida ko'rsatiladi.
• Kirish qismi labirintning yuqori chap burchagida, chiqish qismi esa pastki o'ng qismida joylashgan.

Sizning vazifangiz — berilgan labirintdagi kirish nuqtasidan chiqish nuqtasigacha bo'lgan yagona to'g'ri yo'lni topish va o'sha yo'lning har bir katakdagi markaziy qismiga nuqta \((.)\) belgisini qo'yib, labirintning yakuniy ko'rinishini ekranga chiqarishdan iborat. To'g'ri yo'lga kirmagan boshqa bo'sh joylar o'z holicha qolishi kerak (nuqta qo'yilmaydi).

Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son — labirintning kataklardagi kengligi \(W\) va balandligi \(H\) beriladi (\(1 \le W, H \le 100\)).

Keyingi qatorlarda esa labirintning devorlari va bo'sh joylarini aks ettiruvchi ASCII matnli ko'rinishi keladi.

Chiquvchi ma'lumotlar

Topilgan yagona to'g'ri yo'l katakchalarining markaziga (uchta bo'shliqning o'rtasiga) nuqtalar \((.)\) qo'yilgan holda, labirintning yakuniy matnli ko'rinishini ASCII formatda to'liq chop eting.

Misollar

1

5 3
+---+---+---+---+---+
    |           |   |
+   +   +   +   +   +
|   |   |   |   |   |
+   +   +   +---+   +
|       |
+---+---+---+---+---+

+---+---+---+---+---+
  . | .   .     |   |
+   +   +   +   +   +
| . | . | . |   |   |
+   +   +   +---+   +
| .   . | .   .   .
+---+---+---+---+---+

2

5 5
+---+---+---+---+---+
    |               |
+   +   +   +---+   +
|       |       |   |
+   +---+---+   +---+
|           |       |
+   +---+---+---+   +
|   |           |   |
+   +   +---+   +   +
|   |       |
+---+---+---+---+---+

+---+---+---+---+---+
  . | .   .         |
+   +   +   +---+   +
| .   . | .   . |   |
+   +---+---+   +---+
|           | .   . |
+   +---+---+---+   +
|   |           | . |
+   +   +---+   +   +
|   |       |     .
+---+---+---+---+---+