Заєць 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

Примітка

Ілюстрація в умові показує поле з першого прикладу та напрямки ходів.