Có một ma trận dạng lưới ô vuông gồm \(m\) hàng và \(n\) cột. Các hàng được đánh số từ \(1\) đến \(m\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) theo thứ tự từ trái qua phải. Ô nằm trên hàng \(i\) và cột \(j\) được ký hiệu là \((i, j)\). Một số ô trên lưới có chứa chướng ngại vật, các ô còn lại là ô trống.

Có một con robot di chuyển trên lưới này. Vị trí xuất phát và vị trí kết thúc của con robot là những ô trống đã được cố định từ trước. Con robot được cài sẵn một chuỗi lệnh điều khiển là một xâu ký tự \(C\). Mỗi lệnh của chuỗi là một trong các ký tự U, D, L, R, H. Gọi vị trí hiện tại của robot là \((i, j)\). Ý nghĩa của từng ký tự lệnh như sau:

• U: Đi lên trên \(1\) bước tới ô \((i - 1, j)\)
• D: Đi xuống dưới \(1\) bước tới ô \((i + 1, j)\)
• L: Đi sang trái \(1\) bước tới ô \((i, j - 1)\)
• R: Đi sang phải \(1\) bước tới ô \((i, j + 1)\)
• H: Đứng yên tại ô \((i, j)\)

Con robot sẽ lần lượt thực hiện các lệnh trong chuỗi lệnh \(C\). Chú ý rằng, nếu một lệnh làm con robot đi ra ngoài bảng hoặc đi vào một ô có chướng ngại vật, con robot sẽ bỏ qua và không thực hiện lệnh di chuyển này.

Người ta nhận thấy rằng, nếu xuất phát tại vị trí đã chọn, sau khi thực hiện hết các lệnh trong chuỗi lệnh \(C\), con robot có thể không dừng lại ở vị trí kết thúc đã chọn. Vì vậy, ta cần sửa lại xâu ký tự \(C\) để con robot sẽ dừng lại tại đúng vị trí kết thúc mong muốn sau khi kết thúc thực hiện chuỗi lệnh \(C\). Trong mỗi phép biến đổi, bạn được thực hiện một trong ba thao tác sau:

• Chèn thêm một lệnh vào chuỗi \(C\) ở một vị trí bất kỳ.
• Thay đổi một lệnh bất kỳ trong chuỗi \(C\).
• Xoá đi một chuỗi con liên tiếp bất kỳ của chuỗi \(C\).

Hãy sử dụng ít phép biến đổi nhất có thể để với chuỗi lệnh \(C\), robot sẽ bắt đầu ở vị trí xuất phát đã chọn và kết thúc ở vị trí kết thúc đã chọn. Chú ý rằng, bạn không cần cực tiểu hoá số bước di chuyển của robot, chỉ cần số bước biến đổi chuỗi lệnh là nhỏ nhất có thể. Các ô xuất phát và kết thúc của robot là các ô trống. Trên hành trình của mình, robot có thể đi qua những ô này hay bất kỳ ô trống nào khác một số lần tuỳ ý.

Input

• Dòng đầu tiên chứa số nguyên \(\Theta\) \((1 \leq \Theta \leq 6)\) là số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa hai số nguyên \(m\) và \(n\) \((1 \leq m, n \leq 175)\).
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa một xâu ký tự độ dài \(n\) mô tả một hàng của bảng. Mỗi ký tự của những xâu này có thể là . (dấu chấm thể hiện ô trống), # (ô có chướng ngại vật), S (vị trí xuất phát của robot), E (vị trí kết thúc của robot). Dữ liệu vào đảm bảo có chính xác một chữ S và chính xác một chữ E trong lưới.
• Dòng cuối cùng chứa một xâu ký tự mô tả chuỗi lệnh \(C\) được cài đặt trong robot. Xâu ký tự này chỉ chứa từ 1 đến 300 ký tự, là các chữ cái U, D, L, R và H.

Output

Nếu không tồn tại chuỗi lệnh nào giúp robot đi từ vị trí xuất phát tới vị trí kết thúc, in ra số \(-1\) duy nhất. Ngược lại, dòng đầu tiên chứa số nguyên k là số bước biến đổi chuỗi lệnh tối thiểu. Trong k dòng tiếp theo, mỗi dòng thể hiện một phép biến đổi theo một trong ba khuôn dạng sau:

• INS p c (với \(0 \leq p \leq |C|\) và \(c\) là một trong các chữ cái U, D, L, R và H): Chèn ký tự \(c\) vào sau vị trí \(p\) của chuỗi lệnh. Nếu \(p = 0\), ký tự được chèn vào đầu chuỗi lệnh. Nếu \(p = |C|\), ký tự được chèn vào cuối chuỗi lệnh.
• REP p c (với \(1 \leq p \leq |C|\) và \(c\) là một trong các chữ cái U, D, L, R và H): Thay ký tự ở vị trí \(p\) bởi ký tự \(c\).
• DEL l r (với \(1 \leq l \leq r \leq |C|\)): Xoá đi đoạn lệnh liên tiếp từ vị trí \(l\) tới vị trí \(r\).

Ở đây, \(|C|\) là độ dài chuỗi lệnh trước khi phép biến đổi diễn ra. Chú ý rằng, sau mỗi phép biến đổi, các ký tự của chuỗi lệnh được đánh số lại từ 1.

Nếu có nhiều phương án biến đổi chuỗi lệnh tối ưu, bạn được đưa ra một phương án bất kỳ.

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(14\) điểm): \(m = 1\).
• Subtask \(2\) (\(10.5\) điểm): Chuỗi lệnh \(C\) chỉ chứa ký tự H.
• Subtask \(3\) (\(10.5\) điểm): Dữ liệu vào đảm bảo tồn tại một phương án biến đổi tối ưu mà không cần sử dụng phép biến đổi DEL (xoá một đoạn liên tiếp).
• Subtask \(4\) (\(10.5\) điểm): \(m, n \leq 20\) và chuỗi lệnh ban đầu có không quá \(50\) ký tự.
• Subtask \(5\) (\(10.5\) điểm): \(m,n \leq 50\) và chuỗi lệnh ban đầu có không quá \(100\) ký tự.
• Subtask \(6\) (\(14\) điểm): Không có ràng buộc gì thêm.

Với mỗi test, bạn được 50% số điểm nếu tìm ra số bước biến đổi tối thiểu mà không đưa ra được phương án biến đổi.

Example

4
3 5
....E
S#...
..#..
LRRRDDULLDU

3
REP 1 U
DEL 5 10
INS 5 R

3
3 5
.....
...SE
.....
LLLRRRRRUUD

0

2
3 5
.#..E
..#..
S..#.
HHHHHHHHHHH

-1