In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 20th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #10 exercise sheet]

In this problem you should read from the standard input using functions such as input() and you should write to the standard output using functions such as print()

(you are expected to read the class instructions, that will help you build a solution with structured programming and incremental development)

[IP097] Stranger Cells

(this problem is an adaptation from the contest that selected U. Porto students for MIUP'2024)

Dustin Henderson has always been obsessed with how simple systems can create strange and unpredictable phenomena, especially now that he's seen what the Upside Down is capable of. One evening, while tinkering in his room at Hawkins, he discovers the concept of cellular automata, mathematical models where complex patterns emerge from only a handful of basic rules. Immediately, he's hooked!

He reads about elementary cellular automata and becomes convinced that their evolving patterns might resemble some of the dimensional fluctuations he's been tracking. Determined to test his theory, Dustin sets out to simulate the automaton on his computer. But despite his ingenuity, getting the simulation to run correctly is proving more challenging than expected.

Not one to give up, Dustin turns to you for assistance. He needs a program that can accurately simulate an elementary cellular automaton, generation by generation, starting from an initial configuration.

Dustin's goal is straightforward: he wants to visualize the evolution of the automaton over multiple generations, starting from an initial state, hoping it might reveal clues about the strange behaviors he's been monitoring. Can you help him?

An elementary cellular automaton is a one-dimensional array of cells, where each cell can have one of two states: 0 or 1. The state of a cell in the next generation is determined by the states of itself and its two immediate neighbors (left and right) in the current generation, using a predefined rule.

There are 8 = 2³ possible configurations for a cell and its two immediate neighbors. The rule defining the cellular automaton must specify the resulting state for each of these possibilities, so there are 256 = 2⁸ possible elementary cellular automata. The Wolfram code assigns each rule a number from 0 to 255. Each possible current configuration is written in order, 111, 110, ..., 001, 000, and the resulting state for each of these configurations is written in the same order and interpreted as the binary representation of an integer. This number is taken to be the rule number of the automaton. For example, 30 in decimal is equal to 00011110 in binary, so rule 30 is defined by the transition rule:

It is assumed that the leftmost and the rightmost cells are also adjacent to other unused cells, which are always in state 0. This assumption ensures the automaton rule can be applied in the same way to all cells in the row. The unused cells do not appear in any input or output.

Imagine for instance that we are applying rule 30 to an initial generation that consists of the following (where '.' represents 0 and '#' represents 1):

..#..

Then the next state would be:

.###.

This comes from applying the rule to all cell positions (C) having into acoount its left (L) and right (R) neighbors: LCR

• ..#.. → '.' (current pattern is 000, we apply rule 30, giving origin to 0)
• ..#.. → '#' (current pattern is 001, we apply rule 30, giving origin to 1)
• ..#.. → '#' (current pattern is 010, we apply rule 30, giving origin to 1)
• ..#.. → '#' (current pattern is 100, we apply rule 30, giving origin to 1)
• ..#.. → '.' (current pattern is 000, we apply rule 30, giving origin to 0)

The Problem

Write a program that, given an integer R indicating the rule of the elementary cellular automaton, a number K indicating the number of generations to compute, and a string S indicating the initial state, generates the following K generations as previously described.

Input

The first line of input contains integers separated by a single space: R (the decimal representing the rule) and K (the number of generations)

The second line contains the G, the initial generation, coded as a string of characters, with '.' coding 0 and '#' coding 1. This initial generation will be a single string without spaces.

Output

The output should consist of K lines, containing the following K generations produced by the given automaton. The generations are coded and formatted in the same way as the first generation in the input.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

128 5
#############

.###########.
..#########..
...#######...
....#####....
.....###.....

30 10
...........#...........

..........###..........
.........##..#.........
........##.####........
.......##..#...#.......
......##.####.###......
.....##..#....#..#.....
....##.####..######....
...##..#...###.....#...
..##.####.##..#...###..
.##..#....#.####.##..#.