Trampler

토끼 Trampler는 들판을 짓밟는 것을 좋아한다. 마침 좋은 새 들판을 하나 찾았다. 지도에서 볼 수 있듯이 들판은 높이 $H$칸, 너비 $W$칸인 직사각형이다. Trampler가 어떤 칸에 들어가면 그 칸을 마지막 잔가지까지 짓밟는다. 짓밟는 데는 시간이 걸리며, 그 시간은 칸마다 정해져 있다.

Trampler는 어디서 시작할지 정하지 못했지만, 이동 순서는 이미 정해 두었다. 종이에 적어 두었고, 각 기본 이동을 글자로 표시했다.

이동에는 여러 종류가 있다.

• 글자 'U': 현재 칸에서 바로 위 칸으로 이동한다.
• 글자 'R': 오른쪽으로 인접한 칸으로 이동한다.
• 글자 'L': 왼쪽으로 인접한 칸으로 이동한다.
• 글자 'D': 바로 아래 칸으로 이동한다.

Trampler는 각 칸에 대해, 그 칸에서 짓밟기 경로를 시작했을 때 계획을 수행하는 데 필요한 시간을 알아야 한다. 시작 칸에서도, 이후의 각 칸에서도, 이미 짓밟은 칸이더라도 시간을 쓴다.

끝날 때까지 들판을 떠나지 않을 것이다. 어떤 칸에서 시작하면 결국 들판을 떠나야 한다면, 그 칸은 시작점으로 적합하지 않다. Trampler는 그런 칸을 0으로 표시하려고 한다.

입력 파일의 첫 줄에는 정수 $T$가 주어진다. 이는 테스트 케이스의 수이다 ($1 \le T \le 100$). 이어서 $T$개의 블록이 주어진다.

블록의 첫 줄에는 두 정수 $H$와 $W$가 주어진다. 이는 각각 들판의 높이와 너비이다 ($1 \le H, W \le 100$).

블록의 둘째 줄에는 비어 있지 않은 이동 순서가 주어진다. 각 이동은 'L', 'R', 'U', 'D' 중 하나로 표시된다. 이동의 수는 $100$ 이하이다.

이어지는 $H$개 줄에는 각각 $W$개의 정수가 주어진다. 이는 토끼가 특정 칸에서 보내는 시간이다. 이 수는 $1$ 이상 $1\,000$ 이하이다.

모든 테스트 케이스의 칸 수 합은 $10^5$ 이하이다.

각 테스트 케이스마다 $H$개 줄에 $W$개의 정수를 출력한다. 이는 각 들판 칸에 대한 답이다.

문제의 그림은 첫 번째 예제의 들판과 이동 방향을 보여 준다.