Chú thỏ rừng Trampler rất thích giẫm nát các cánh đồng. Chú vừa tìm được một cánh đồng mới rất tốt. Như trên bản đồ, cánh đồng là một hình chữ nhật cao $H$ ô và rộng $W$ ô. Khi Trampler vào một ô, chú giẫm nát nó đến tận cành cây cuối cùng. Việc này mất một khoảng thời gian, được xác định riêng cho từng ô.

Trampler chưa biết bắt đầu từ đâu, nhưng đã xác định được thứ tự di chuyển. Chú đã viết nguệch ngoạc nó lên một mảnh giấy, dùng một chữ cái để đánh dấu mỗi bước di chuyển cơ bản.

Có các loại bước di chuyển khác nhau:

• chữ U: di chuyển từ ô hiện tại của cánh đồng đến ô liền kề ngay phía trên;
• chữ R: di chuyển đến ô liền kề bên phải;
• chữ L: di chuyển đến ô liền kề bên trái;
• chữ D: di chuyển đến ô liền kề phía dưới.

Với mỗi ô, Trampler cần biết thời gian cần thiết để thực hiện kế hoạch nếu bắt đầu lộ trình giẫm nát từ ô đó. Chú sẽ tốn thời gian ở ô ban đầu và mỗi ô tiếp theo, kể cả khi ô đó đã bị giẫm nát trước đó.

Chú không định rời cánh đồng trước khi làm xong. Nếu bắt đầu tại một ô nào đó khiến chú cuối cùng phải rời khỏi cánh đồng, ô đó không phù hợp làm điểm bắt đầu. Trampler muốn các ô như vậy được đánh dấu bằng $0$.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào cho một số nguyên $T$ — số lượng bộ dữ liệu kiểm tra ($1 \le T \le 100$). Tiếp theo là $T$ khối.

Dòng đầu tiên của một khối chứa hai số nguyên $H$ và $W$ — chiều cao và chiều rộng của cánh đồng, tương ứng ($1 \le H, W \le 100$).

Dòng thứ hai của khối chứa một dãy bước di chuyển không rỗng. Mỗi bước được biểu diễn bằng một trong các ký tự L, R, U, D. Số bước không vượt quá $100$.

Mỗi dòng trong $H$ dòng tiếp theo chứa $W$ số nguyên — thời gian chú thỏ ở trong từng ô cụ thể của cánh đồng. Các số này nằm trong khoảng từ $1$ đến $1\,000$.

Tổng số ô trong tất cả các bộ dữ liệu kiểm tra không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu kiểm tra, in $H$ dòng, mỗi dòng $W$ số nguyên — câu trả lời cho từng ô của cánh đồng.

Ví dụ

Dữ liệu vào 1

1
3 4
RDRUL
2 9 7 4
5 8 6 5
6 4 6 2

Dữ liệu ra 1

41 38 0 0
37 33 0 0
0 0 0 0

Dữ liệu vào 2

2
1 1
D
1
5 5
RLDULRUD
4 7 8 5 8
7 9 9 5 7
3 8 5 3 6
1 6 6 9 3
5 2 1 6 1

Dữ liệu ra 2

0
0 0 0 0 0
0 76 72 49 0
0 63 51 40 0
0 47 51 63 0
0 0 0 0 0

Ghi chú

Hình minh họa trong đề bài biểu diễn cánh đồng của ví dụ đầu tiên và các hướng di chuyển.