The game of the life

The english mathematician John Conway invented in 1970 the following game:

Imagine a matrix with $n$ rows and $m$ columns. The (at most, eight) positions which are at distance 1, horizontally, vertically or in diagonal are considered adjacent positions. In each moment, each position of the matrix is empty or contains a tree. The rules are:

• An empty position in a moment $t$ will contain a tree at the moment $t + 1$ if and only if at the moment $t$ had exactly three adjacent trees.

• An occupied position at the moment $t$ will contain a tree at the moment $t + 1$ if and only if at the moment $t$ had two or three adjacent trees.

Your task is to write a program that, for each given matrix, prints the matrix at the posterior moment of time.

Input

The input consists of zero or more cases. Each case consists of a line with $N$ and $M$ (two integers between 1 and 100) followed by $N$ lines (one per row) each one with $M$ characters: X if the position is occupied and . if the position is empty. A line with $N = M = 0$ indicates the end of the input.

Output

For each case, your program must print the matrix corresponding to the next moment using the same format than the one of the input. It must print a line feed after each matrix.

Author

Salvador Roura (en: Carlos Molina)

© Jutge.org, 2006–2025.