Wall

Tomorrow Programming School will decorate the front wall of its entrance hall with a pattern produced by an elementary cellular automaton. The designers will study the outputs of several automata and choose the one they like most.

Your task is to write a program that reproduces the output of an automaton.

An elementary cellular automaton is a row of adjacent cells and a rewriting rule. Each cell is in state 0 or 1. The sequence of states of all cells, in row order, is called a generation.

The automaton runs in cycles. In each cycle, the program takes the current generation as input, applies the rule to every cell, and computes a new generation. At the end of the cycle, the new generation replaces the current one. The cycle can be repeated any number of times.

The leftmost and rightmost cells are also adjacent to unused cells, which always have state 0. This lets the rule apply in the same way to every cell. Unused cells never appear in the input or output.

The new state of a cell C depends on its own state and the states of its left and right neighbors in the current generation, through the rule. A triple of states has $2^3 = 8$ possibilities, which are listed as $S = (111, 110, 101, 100, 011, 010, 001, 000)$. The middle digit is the state of C, and the first and third digits are the states of its left and right neighbors.

The rule assigns one bit, 0 or 1, to each of the eight triples in S. The bits, read in the order of S, form an 8-bit vector. The rule number is this vector written in decimal. S itself is not part of the rule number.

To apply the rule to C, find the triple in S that matches C and its two neighbors in the current generation. The bit assigned to that triple is the new state of C.

There are $2^8 = 256$ different automata, one for each rule number.

The first line contains two integers R and K (0 ≤ R ≤ 255, 1 ≤ K ≤ 200), the rule number in decimal and the number of generations. The second line contains the first generation. A . stands for state 0 and an X stands for state 1. The generation is given as one string without spaces. Its width is at least 1 and at most 250 cells.

Print the K generations produced by the automaton after the first one. Each generation uses the same format as the first generation in the input and occupies one line. Do not print empty lines.