Problems
Minimal Matrix
Minimal Matrix
Research Institute of Given Strings is opening a new department - Research Deparment of Given Matrices. Similarly to a problem of string canonization the new deparment is now working on a problem of matrix canonization.
Consider a matrix \textbf{m_\{i,j\}} of size \textbf{2^n}× \textbf{2^n} containing lowercase letters.
The circular shift of a matrix \textbf{m} is a matrix \textbf{m'} such that \textbf{m'_\{i,j\} = m_\{(i+Δi) mod 2^n, (j+Δj) mod 2^n\}} from some Δ\textbf{i} and Δ\textbf{j }(matrices are indexed from \textbf{0} to \textbf{2^n-1}).
Matrix \textbf{p} is lexicographically less than matrix \textbf{q} of the same size if there are some \textbf{i} and \textbf{j} such that for \textbf{i'} < \textbf{i}, or \textbf{i'} = \textbf{i} and \textbf{j'} < \textbf{j} the equality \textbf{p_\{i',j'\}} = \textbf{q_\{i',j'\}} holds, and \textbf{p_\{i,j\}} < \textbf{q_\{i,j\}}. That is, we compare matrices by rows.
Given matrix \textbf{m}, the problem of its canonization is to find its circular shift such that it is lexicographically less or equal to any other circular shift of \textbf{m}.
Help the researchers in the new department to find the canonization of a given matrix.
\InputFile
The input file contains a matrix \textbf{m}. Its size if \textbf{2^n}× \textbf{2^n} , \textbf{0} ≤ \textbf{n} ≤ \textbf{9}.
\OutputFile
Output the canonization of the given matrix.
Input example #1
baba baab abba bbba
Output example #1
aabb abbb abab bbaa