הארנב 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

הערה

האיור בתיאור הבעיה מציג את השדה מהדוגמה הראשונה ואת כיווני התנועות.