Kelinci liar Trampler suka menginjak-injak ladang. Ia baru saja menemukan ladang baru yang bagus. Seperti terlihat pada peta, ladang itu berbentuk persegi panjang dengan tinggi $H$ sel dan lebar $W$ sel. Ketika Trampler memasuki sebuah sel, ia menginjak-injaknya hingga ranting terakhir. Hal itu memerlukan waktu, yang ditentukan secara khusus untuk setiap sel.

Trampler belum yakin harus mulai dari mana, tetapi ia sudah menentukan urutan gerakannya. Ia mencoretkannya pada selembar kertas, menandai setiap gerakan dasar dengan sebuah huruf.

Ada beberapa jenis gerakan:

• huruf U: bergerak dari sel ladang saat ini ke sel yang tepat bersebelahan di atasnya;
• huruf R: bergerak ke sel yang bersebelahan di kanan;
• huruf L: bergerak ke sel yang bersebelahan di kiri;
• huruf D: bergerak ke sel yang bersebelahan di bawah.

Untuk setiap sel, Trampler perlu mengetahui waktu yang diperlukan untuk menjalankan rencananya jika ia memulai rute menginjak-injak dari sel tersebut. Ia akan menghabiskan waktu di sel awal dan di setiap sel berikutnya, sekalipun sel tersebut sudah pernah diinjak-injak.

Ia tidak berencana meninggalkan ladang sebelum selesai. Jika memulai pada suatu sel membuatnya harus meninggalkan ladang pada akhirnya, sel tersebut tidak cocok sebagai titik awal. Trampler ingin sel-sel seperti itu ditandai dengan $0$.

Masukan

Baris pertama berkas masukan menentukan sebuah bilangan bulat $T$ — banyaknya kasus uji ($1 \le T \le 100$). Setelah itu terdapat $T$ blok.

Baris pertama sebuah blok berisi dua bilangan bulat $H$ dan $W$ — tinggi dan lebar ladang, secara berurutan ($1 \le H, W \le 100$).

Baris kedua blok berisi sebuah urutan gerakan yang tidak kosong. Setiap gerakan dinyatakan oleh salah satu simbol L, R, U, D. Banyaknya gerakan paling besar $100$.

Masing-masing dari $H$ baris berikutnya berisi $W$ bilangan bulat — waktu yang dihabiskan kelinci pada sel tertentu di ladang. Bilangan-bilangan ini berada pada rentang $1$ hingga $1\,000$.

Jumlah seluruh sel pada semua kasus uji paling besar $10^5$.

Keluaran

Untuk setiap kasus uji, cetak $H$ baris dengan $W$ bilangan bulat pada setiap baris — jawaban untuk setiap sel ladang.

Contoh

Masukan 1

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

Keluaran 1

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

Masukan 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

Keluaran 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

Catatan

Ilustrasi pada soal memperlihatkan ladang dari contoh pertama dan arah gerakan.