يحب الأرنب البري 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

ملاحظة

يوضح الرسم في نص المسألة الحقل من المثال الأول واتجاهات الحركات.