Минимальная матрица
Исследовательский Институт Данных Строк открыл новый отдел - Отдел Исследования Заданных Матриц. Аналогично задаче канонизации строк, отдел работает над задачей канонизации матриц.
Рассмотрим матрицу m_{i,j} размера 2^n× 2^n, содержащую буквы нижнего регистра.
Циклическим сдвигом матрицы m называется такая матрица m', что m'_{i,j} = m_{(i+Δi) mod 2^n, (j+Δj) mod 2^n} для некоторых Δi и Δj (строки и столбцы матрицы проиндексированы от 0 до 2^n-1).
Матрица p является лексикографически меньше матрицы q, имеющей тот же размер, если существуют такие i и j, что для i' < i, или для i' = i и j' < j имеет место равенство p_{i',j'} = q_{i',j'}, а p_{i,j} < q_{i,j}. То есть сравнение матриц происходит построчно.
Задача канонизации матрицы m состоит в нахождении такого циклического сдвига, который будет не больше любого другого циклического сдвига m.
Помогите исследователям нового отдела найти каноническое представление матрицы.
Входные данные
Матрица m, имеющая размер 2^n× 2^n (0 ≤ n ≤ 9).
Выходные данные
Вывести каноническое представление матрицы m.