Game of Life

Life is beautiful, both sad and happy moments are all part of it. Unfortunately we people tend to be selfish and only care about ourselves, and sometimes we even forget that other lifeforms are just as important in terms of the planet as we are. Thus for this exercise we are paying a tribute to the itsy-bitsy cells surrounding us.
We are provided with a colony of cells in a Petri-dish which is arranged in a table-like structure. Empty fields are denoted with a o character and living cells with an x character. Your task is to print out the state of the Petri-dish starting from a given initial state after a given number of iterations.
Each iteration is calculated by the following rules:

• every new iteration is calculated by using the actual state of the dish. Iterations happen instantly.
• if a cell has less than 2 neighbouring cells (cells which are 1 distance away from it), then it dies, so in the next iteration its field will be empty
• if a cell has 2-3 neighbouring cells, then it will stay alive
• if a cell has more than 3 neighbours, then it dies due to overpopulation
• if an empty field has exactly 3 cells in its direct neighbourhood, then in the next iteration that field will be populated by a cell

Input

The input has 3 parts:

• The first line contains a positive n integer which tells you the width and height of the square Petri-dish. The top left field has an index of (0,0), and the indexing increases by 1 to the left and down.
• The next line contains the number of I iterations which is a non-negative integer. The starting state can be considered as the 0th iteration.
• Each of the next n lines contains a string of length n which describes the starting state of the Petri-dish. Te string can only contain the characters o and x.

Output

The output should be n lines, each of length n which describes the state of the Petri-dish after I iterations.

Restrictions

Example