Tuổi thơ của chúng ta có lẽ đã quá quen thuộc với Trò chơi pacman. Ở trò chơi này, pacman và "ma" cùng được đặt trong một ma trận chứa đầy vàng, trước mỗi level người chơi sẽ tiến hành đặt ra lịch trình di chuyển cho nhân vật pacman của mình, còn Computer sẽ tự động sinh ra lịch trình di chuyển cho ma.

Ma trận chơi là một hình vuông kích thước N*N, cả pacman và ma chỉ được phép hoạt động trong phạm vi của ma trận này. Viền bao của ma trận được đánh dấu là số 0, bên trong chứa các số Nguyên dương cho biết lượng vàng có tại vị trị (i, j) tương ứng. Nếu pacman hoặc ma đã ăn vàng tại vị trí (i, j) thì ô này sẽ ngay lập tức không còn vàng nữa. Trò chơi sẽ kết thúc khi chuỗi lập lịch của người chơi cho pacman và Computer cho ma hết hoặc cả 2 đâm đầu vào nhau.

Trò chơi bắt đầu, pacman được đặt ở vị trí trên cùng bên trái (0, 0) của hình vuông N*N với chiều di chuyển ban đầu là hướng xuống dưới, còn ma được đặt ở vị trí dưới cùng bên phải (N-1, N-1) của ma trận với chiều di chuyển ban đầu là hướng lên trên.

Nhiệm vụ của bạn là phải tạo một chương trình tính toán nhanh tổng lượng vàng mà pacman và ma có thể thu được trước khi trò chơi kết thúc.

Input

Dòng đầu tiên là số lượng testcase T của bài toán (1 <= T <= 100)

Dòng đầu tiên của mỗi testcase là 2 số N, M (5 <= N <= 100; 5 <= M <= 300) lần lượt mô tả kích thước của ma trận chơi và độ dài của chuỗi lập lịch ban đầu.

N dòng tiếp theo, mỗi dòng chứa N số nguyên dương biểu thị ma trận chơi.

Dòng thứ N+1 trong mỗi testcase là chuỗi M ký tự cho biết lịch trình di chuyển của pacman.

Dòng thứ N+2 trong mỗi tescase là chuỗi M ký tự cho biết lịch trình di chuyển của ma.

M ký tự này có 3 trạng thái sau: C - tiếp tục di chuyển theo hướng hiện tại với cự li 1 ô, L - tiến hành rẽ trái 1 ô và đi đến ô đó, R - tiền hành rẽ phải 1 ô và đi đến ô đó.

(Dữ liệu đảm bảo pacman và ma không đi ra ngoài phạm vi của ma trận chơi)

Output

Mỗi testcase được in trên 1 dòng với format sau: mở đầu là ký tự '#', tiếp theo là số thứ tự của testcase, theo sau là 1 dấu cách (khoảng trắng), tiếp theo là số lượng vàng mà pacman và ma thu được (cách nhau bới 1 dấu cách)

Example

Input:
2
6 6
0 0 0 0 0 0
0 1 7 8 5 0
0 1 5 4 3 0
0 7 5 5 6 0
0 8 9 9 5 0
0 0 0 0 0 0
CCLLRL
CLLLLL
6 15
0 0 0 0 0 0
0 9 3 3 8 0
0 1 8 5 2 0
0 1 3 9 5 0
0 9 2 1 3 0
0 0 0 0 0 0
CCLLRCRCCCLLRLC
CCCLCRCRCRCCCCR

Output:
#1 9 5
#2 13 7