Tom đang khám phá trò chơi trên máy chơi game cầm tay vừa được bạn tặng nhân ngày sinh nhật. Màn hình trò chơi gồm ~N \times N~ ô vuông nhỏ, xếp thành ~N~ hàng và ~N~ cột. Bắt đầu trò chơi, có một trái banh nằm trên ~1~ ô vuông nhỏ, các ô vuông nhỏ khác hoặc là trống, hoặc là có một viên gạch chiếm hết diện tích ô. Dưới tác dụng của trọng lực, trái banh luôn nằm trên viên gạch hoặc trên đường biên dưới của màn hình.
Khi Tom nhấn nút quay ~90~ độ cùng chiều hoặc ngược chiều kim đồng hồ thì các viên gạch và trái bóng cùng với màn hình quay ~90~ độ cùng chiều hoặc ngược chiều kim đồng hồ. Sau khi quay, trái banh rơi xuống (do tác dụng của trọng lực) nằm trên viên gạch đầu tiên bên dưới nó hoặc rớt xuống đường biên dưới của màn hình.
Ví dụ: Hình bên dưới minh họa màn hình bắt đầu trò chơi và sau khi nhấn nút quay cùng chiều và ngược chiều kim đồng hồ.
Yêu cầu:
Hãy xác định trạng thái của màn hình trò chơi sau một dãy ~K~ thao tác quay cho trước.
Dữ liệu vào:
- Dòng đầu tiên chứa ~2~ số ~N~ và ~K~ ~(1 ≤ N ≤ 1000, 1 ≤ K ≤ 500000)~.
- ~N~ dòng tiếp theo mô tả màn hình ban đầu của trò chơi: dấu chấm
.
kí hiệu ô rỗng,X
kí hiệu là viên gạch vàL
là vị trí ban đầu của trái banh. - ~K~ dòng tiếp theo, mỗi dòng chứa một kí tự,
L
hoặcD
, vớiL
: quay ngược chiều kim đồng hồ vàD
: quay cùng chiều kim đồng hồ.
Kết quả ra:
Gồm ~N~ dòng mô tả trạng thái màn hình trò chơi sau khi thực hiện ~K~ thao tác quay đã cho.
Sample Input
6 2
....XX
X.....
......
..L...
.XXX..
......
L
D
Sample Output
....XX
X.....
......
......
.XXX..
L.....
Bình luận