Game of the life (2) P27283

This exercise is a continuation of the exercise problem://problemsjutge.org:problems/p1/roura/vida-1.pbm

Let $M_0$ be a matrix with bacteria at the initial time, and let $M_1$, $M_2$, $M_3$, … be the matrices at the times 1, 2, 3, … Write a program that, given $M_0$, finds the cycle that is obtained starting at $M_0$, that is, the first and shortest sequence of matrices $M_i, M_{i+1}, \dots, M_{j-1}, M_j$ such that $M_{j+1} = M_i$. Suppose $j < 100$.

Input

Input consists of the description of the matrix $M_0$: two strictly positive natural numbers $n$ and $m$, followed by $n$ lines, each one with $m$ characters: ‘B’ if the position has a bacterium, and ‘.’ if the position is empty.

Output

Print the matrices of the cycle $M_i, M_{i+1}, \dots, M_{j-1}, M_j$ separated by an empty line.