Мінімальна матриця

Дослідницький інститут даних рядків відкрив новий підрозділ — Дослідницький відділ даних матриць. Аналогічно до задачі канонізації рядків, цей відділ працює над проблемою канонізації матриць.

Розглянемо матрицю m_{i,j} розміром 2^n \times 2^n, яка містить малі латинські літери.

Циклічний зсув матриці $m$ — це матриця m', така що m'_{i,j} = m_{(i+\Delta i) \bmod 2^n,\ (j+\Delta j) \bmod 2^n} для деяких $\Delta i$ та $\Delta 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$.

Допоможіть дослідникам нового відділу знайти канонічне представлення матриці.