Minimal Matrix#3075

Minimal Matrix

2 seconds

256 megabytes

Medium

Research Institute of Given Strings has opened a new department — Research Department of Given Matrices. Similarly to the problem of string canonization, this department is working on the problem of matrix canonization.

Consider a matrix $m_{i, j}$ m_{i,j} of size $2^{n} \times 2^{n}$ 2^n \times 2^n, containing lowercase Latin letters.

A circular shift of a matrix $m$ is a matrix $m^{'}$ m' such that $m_{i, j}^{'} = m_{(i + Δ i) mod 2^{n}, (j + Δ j) mod 2^{n}}$ m'_{i,j} = m_{(i + \Delta i)\bmod 2^n,\ (j + \Delta j)\bmod 2^n} for some $Δ i$ and $Δ j$ (the rows and columns of the matrix are indexed from $0$ to $2^{n} - 1$ 2^n - 1).

Matrix $p$ is lexicographically less than matrix $q$ of the same size, if there exist $i$ and $j$ , such that for all $i^{'} < i$ i' < i, or for $i^{'} = i$ i' = i and $j^{'} < j$ j' < j, $p_{i^{'}, j^{'}} = q_{i^{'}, j^{'}}$ p_{i',j'} = q_{i',j'}, and $p_{i, j} < q_{i, j}$ p_{i,j} < q_{i,j}. That is, matrices are compared row by row.

The canonization problem for matrix $m$ is to find such a circular shift of $m$ that is lexicographically less than or equal to any other circular shift of $m$ .

Help the researchers of the new department find the canonical representation of the matrix.

Input

The matrix $m$ , of size $2^{n} \times 2^{n}$ 2^n \times 2^n ( $0 \leq n \leq 9$ 0 \leq n \leq 9).

Output

Output the canonical representation of matrix $m$ .

Examples

Example 1

Loading

m_{i, j}

2^{n} \times 2^{n}

m^{'}

m_{i, j}^{'} = m_{(i + Δ i) mod 2^{n}, (j + Δ j) mod 2^{n}}

2^{n} - 1

i^{'} < i

i^{'} = i

j^{'} < j

p_{i^{'}, j^{'}} = q_{i^{'}, j^{'}}

p_{i, j} < q_{i, j}

2^{n} \times 2^{n}

0 \leq n \leq 9