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 m_{i,j} of size 2^n× 2^n containing lowercase letters.
The circular shift of a matrix m is a matrix m' such that m'_{i,j} = m_{(i+Δi) mod 2^n, (j+Δj) mod 2^n} from some Δi and Δj (matrices are indexed from 0 to 2^n-1).
Matrix p is lexicographically less than matrix q of the same size if there are some i and j such that for i' < i, or i' = i and j' < j the equality p_{i',j'} = q_{i',j'} holds, and p_{i,j} < q_{i,j}. That is, we compare matrices by rows.
Given matrix 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 m.
Help the researchers in the new department to find the canonization of a given matrix.
The input file contains a matrix m. Its size if 2^n× 2^n , 0 ≤ n ≤ 9.
Output the canonization of the given matrix.