Robot Điên

Có một lưới gồm $n$ hàng và $m$ cột. Mỗi ô của lưới hoặc trống hoặc bị chặn. Một ô trống chứa phòng thí nghiệm. Tất cả các ô nằm ngoài biên của lưới cũng được coi là bị chặn.

Một con robot điên đã trốn khỏi phòng thí nghiệm. Hiện tại nó đang ở một ô trống nào đó. Bạn có thể gửi cho robot một trong các lệnh sau: "sang phải", "xuống dưới", "sang trái" hoặc "lên trên". Mỗi lệnh yêu cầu robot di chuyển sang ô kề theo hướng tương ứng.

Tuy nhiên vì robot bị điên, nó sẽ làm mọi thứ trừ việc tuân theo lệnh. Khi nhận một lệnh, robot sẽ chọn một hướng khác với hướng trong lệnh sao cho ô theo hướng đó không bị chặn, rồi di chuyển sang ô kề đó. Nếu có nhiều hướng như vậy, robot tự chọn một hướng bất kỳ trong số đó. Nếu không có hướng nào thỏa mãn, robot đứng yên.

Ta muốn đưa robot về phòng thí nghiệm để sửa. Với mỗi ô trống, hãy xác định xem robot có thể bị buộc phải về phòng thí nghiệm nếu xuất phát từ ô đó hay không. Nghĩa là, sau mỗi bước của robot ta luôn có thể chọn một lệnh để gửi, sao cho dù robot chọn hướng nào (khác hướng lệnh) đi nữa thì cuối cùng nó vẫn đến được phòng thí nghiệm.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ (số bộ dữ liệu).
• Mỗi bộ dữ liệu:
  • Dòng đầu chứa hai số nguyên $n$ và $m$ (số hàng và số cột).
  • $n$ dòng tiếp theo mô tả lưới, mỗi dòng gồm $m$ ký tự thuộc một trong ba loại:
    • . — ô trống;
    • # — ô bị chặn;
    • L — ô chứa phòng thí nghiệm.

Lưới chứa đúng một phòng thí nghiệm.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra lưới kết quả: thay các ô trống (ký tự .) mà robot có thể bị buộc về phòng thí nghiệm bằng dấu cộng (+). Các ô còn lại giữ nguyên.

Ràng buộc

• $1\le t\le 1000$
• $1\le n,m\le {10}^6$ và $n·m\le {10}^6$
• Tổng $n·m$ trên tất cả các bộ dữ liệu không vượt quá ${10}^6$.

Ví dụ