Məsələlər
Минимальная матрица
Минимальная матрица
Исследовательский Институт Данных Строк открыл новый отдел - Отдел Исследования Заданных Матриц. Аналогично задаче канонизации строк, отдел работает над задачей канонизации матриц.
Рассмотрим матрицу \textbf{m_\{i,j\}} размера \textbf{2^n}× \textbf{2^n}, содержащую буквы нижнего регистра.
Циклическим сдвигом матрицы \textbf{m} называется такая матрица \textbf{m'}, что \textbf{m'_\{i,j\} = m_\{(i+Δi) mod 2^n, (j+Δj) mod 2^n\}} для некоторых Δ\textbf{i} и Δ\textbf{j }(строки и столбцы матрицы проиндексированы от \textbf{0} до \textbf{2^n-1}).
Матрица \textbf{p} является лексикографически меньше матрицы \textbf{q}, имеющей тот же размер, если существуют такие \textbf{i} и \textbf{j}, что для \textbf{i'} < \textbf{i}, или для \textbf{i'} = \textbf{i} и \textbf{j'} <\textbf{ j} имеет место равенство \textbf{p_\{i',j'\}} = \textbf{q_\{i',j'\}}, а \textbf{p_\{i,j\}} < \textbf{q_\{i,j\}}. То есть сравнение матриц происходит построчно.
Задача канонизации матрицы \textbf{m} состоит в нахождении такого циклического сдвига, который будет не больше любого другого циклического сдвига \textbf{m}.
Помогите исследователям нового отдела найти каноническое представление матрицы.
\InputFile
Матрица \textbf{m}, имеющая размер \textbf{2^n}× \textbf{2^n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{9}).
\OutputFile
Вывести каноническое представление матрицы \textbf{m}.
Giriş verilənləri #1
baba baab abba bbba
Çıxış verilənləri #1
aabb abbb abab bbaa