E. Сумасшедший робот
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана поле, состоящая из $$$n$$$ строк и $$$m$$$ столбцов. Каждая ячейка матрица либо свободна, либо занята. В одной из свободных клеток находится лаборатория. Все ячейки за границами поля заблокированы.

Сумасшедший робот сбежал из лаборатории. В данный момент он находится в некоторой свободной клетке. Вы можете послать ему одну из следующих команд: «идти вправо», «идти вниз», «идти влево» или «идти вверх». Каждая команда означает переход в соседнюю клетку в соответствующем направлении.

Однако, так как робот сумасшедший, он сделает что угодно, кроме выполнения команды. При получении команды, он выберет такое направление, что оно отличается от данного в команде, и ячейка в выбранном направлении не занята. Если есть такое направление, то он переместится в этом направлении. Иначе, он не сделает ничего.

Мы хотим привести робота обратно в лаборатории, чтобы его починить. Для каждой свободной клетке определите, можно ли заставить робота достичь лаборатории, если он начнет в этой клетке. То есть, после каждого шага работа можно будет послать такую команду, что какие бы направления робот ни выбирал, он окажется в лаборатории.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^6$$$; $$$n \cdot m \le 10^6$$$) — количество строк и столбцов поля.

В $$$i$$$-й из следующих $$$n$$$ строк задается описание $$$i$$$-й строки поля. Она состоит из $$$m$$$ элементов одного из трех типов:

  • '.' — ячейка свободна;
  • '#' — ячейка занята;
  • 'L' — ячейка содержит лабораторию.

Поле содержит ровно одну лабораторию. Сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

На каждый набор входных данных найдите все свободные клетки, из которых можно заставить робота дойти до лаборатории. В заданном поле замените свободные клетки (обозначенные точкой) знаком плюса ('+') в тех клетках, из которых можно заставить робота дойти до лаборатории. Выведите получившееся поле.

Пример
Входные данные
4
3 3
...
.L.
...
4 5
#....
..##L
...#.
.....
1 1
L
1 9
....L..#.
Выходные данные
...
.L.
...
#++++
..##L
...#+
...++
L
++++L++#.
Примечание

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

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