C. Латинский квадрат
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана квадратная матрица размера $$$n$$$. В каждой строке и каждом столбце этой матрицы записана перестановка чисел $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$. Пусть $$$a_{i, j}$$$ означает число на пересечении $$$i$$$-й строки и $$$j$$$-го столбца для всех $$$1 \leq i, j \leq n$$$. Строки нумеруются $$$1, \ldots, n$$$ сверху вниз, а столбцы нумеруются $$$1, \ldots, n$$$ слева направо.

Мы совершаем операции шести типов:

  • R: циклически сдвинуть все столбцы вправо, формально, заменить значение каждого $$$a_{i, j}$$$ на $$$a_{i, ((j - 2)\bmod n) + 1}$$$;
  • L: циклически сдвинуть все столбцы влево, формально, заменить значение каждого $$$a_{i, j}$$$ на $$$a_{i, (j\bmod n) + 1}$$$;
  • D: циклически сдвинуть все строки вниз, формально, заменить значение каждого $$$a_{i, j}$$$ на $$$a_{((i - 2)\bmod n) + 1, j}$$$;
  • U: циклически сдвинуть все строки вверх, формально, заменить значение каждого $$$a_{i, j}$$$ на $$$a_{(i\bmod n) + 1, j}$$$;
  • I: заменить перестановку, которую можно прочитать в каждой строке слева направо, на обратную;
  • C: заменить перестановку, которую можно прочитать в каждом столбце сверху вниз, на обратную.

Обратной к перестановке $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ является перестановка $$$q_1$$$, $$$q_2$$$, $$$\ldots$$$, $$$q_n$$$, такая что $$$p_{q_i} = i$$$ для каждого $$$1 \leq i \leq n$$$.

Можно показать, что после любой последовательности операций любая строка и любой столбец матрицы всё ещё будет содержать перестановку чисел $$$1, 2, \ldots, n$$$.

Вам дано описание исходной матрицы. Нужно совершить $$$m$$$ операций и вывести получившееся состояние матрицы.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество тестовых примеров. Далее следует описание $$$t$$$ примеров.

Первого строка описания каждого примера содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 1000, 1 \leq m \leq 10^5$$$) — размер матрицы и количество операций.

Каждая из следующих $$$n$$$ строк содержит по $$$n$$$ целых чисел через пробел — элементы матрицы $$$a$$$ ($$$1 \leq a_{i, j} \leq n$$$).

В последней строке описания записано $$$m$$$ символов, описывающих операции по порядку в формате, описанном выше.

Сумма всех $$$n$$$ не превосходит $$$1000$$$, а сумма всех $$$m$$$ не превосходит $$$10^5$$$.

Выходные данные

Для каждого примера выведите $$$n$$$ строк, по $$$n$$$ чисел в каждой — получившееся состояние матрицы после $$$m$$$ операций.

Пример
Входные данные
5
3 2
1 2 3
2 3 1
3 1 2
DR
3 2
1 2 3
2 3 1
3 1 2
LU
3 1
1 2 3
2 3 1
3 1 2
I
3 1
1 2 3
2 3 1
3 1 2
C
3 16
1 2 3
2 3 1
3 1 2
LDICRUCILDICRUCI
Выходные данные
2 3 1 
3 1 2 
1 2 3 

3 1 2 
1 2 3 
2 3 1 

1 2 3 
3 1 2 
2 3 1 

1 3 2 
2 1 3 
3 2 1 

2 3 1 
3 1 2 
1 2 3
Примечание

Лишние переводы строк между ответами для примера выше добавлены для наглядности, выводить их необязательно.