A long time ago John Conway invented a cellular automaton 'game'. The game consists of a grid with cells that are either 'dead' or 'alive'. Each 'generation' the cells die or become alive based on their neighbours.

The rules:

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Imagine you are a computer, your job is to compute the next G generations of the cells based on the input of the current state, according to the rules.

Input:

An integer N that tells you the size of the grid, which is N x N.

An integer G that tells you how many generations you need to compute.

A grid of cells represented by * for alive and - for dead.

Output:

G lines of grids representing the next generations of cells, each followed by a line-break.

Constraints:

3 <= N <= 70

1 <= G <= 50