Заяц 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

Примечание

Иллюстрация в условии показывает поле из первого примера и направления ходов.