Simulating the Game of life X13387

The English mathematician John Conway invented in 1970 the so called "Game of life" as follows: Imagine a square matrix with n rows and n columns with free positions and positions occupied by a bacterium. The game considers the evolution of bacteria with local rules.

From a matrix position, there are considered adjacent positions the (at most eight) positions found at distance one either horizontally, vertically or diagonally. At every moment, every position of the matrix is either empty or contains a bacterium. The rules of the game are the following:

• An empty position in an instant t contains a bacterium at time t + 1 if and only if at time t it has exactly three adjacent bacteria.
• An occupied position in an instant t contains a bacterium at time t + 1 if and only if at time t it has two or more adjacent bacteria.

We want to make a sequential simulation of the evolution of the game in such a way that, at every moment, only one position is updated. The sequence of positions follows a zig-zag traversal by columns, starting at the upper left position, (0,0), and walking the first column downwards ((0,0) to (n−1,0)), the second column upwards ((n−1,1) to (0,1)), and so on.

We call a round a complete traversal of all the positions in the matrix, following the zig-zag traversal by columns.

Write a program that, for each given matrix and number of rounds, computes the matrix of the game after the stipulated number of rounds.

Note that if after a certain round the matrix has not changed, it will never change again.

Input

The input is formed by two natural numbers n > 0, the size of the matrix, and r>0, the number of rounds. Followed by a list of positions, pairs of integers between 0 and n −1 , indicating the positions of the bacteria .

Output

Write, for each initial configuration, which is the initial matrix of the game and all the intermediate matrices (after each simulation round), with an empty line after each matrix. Follow the format of the examples .

Observation

Note that, if the matrix after a simulation round has not changed, you should not write this matrix more than twice.