กระต่ายป่า 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$ จำนวน คือคำตอบสำหรับแต่ละช่องของทุ่งนา

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

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

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 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

หมายเหตุ

ภาพประกอบในโจทย์แสดงทุ่งนาจากตัวอย่างแรกและทิศทางการเคลื่อนที่