Codeforces Round 691 (Div. 1) |
---|
Закончено |
Вам дана квадратная матрица размера $$$n$$$. В каждой строке и каждом столбце этой матрицы записана перестановка чисел $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$. Пусть $$$a_{i, j}$$$ означает число на пересечении $$$i$$$-й строки и $$$j$$$-го столбца для всех $$$1 \leq i, j \leq n$$$. Строки нумеруются $$$1, \ldots, n$$$ сверху вниз, а столбцы нумеруются $$$1, \ldots, n$$$ слева направо.
Мы совершаем операции шести типов:
Обратной к перестановке $$$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
Лишние переводы строк между ответами для примера выше добавлены для наглядности, выводить их необязательно.
Название |
---|