In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 21st
(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)

[IP093] The Mysteries of Cellular Automata

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

Sakura Haruno has always been curious about how simple rules can give rise to complex patterns. One day, she stumbles upon the concept of cellular automata and is immediately fascinated by their beauty and potential. She reads about elementary cellular automata, where intricate designs emerge from just a few basic rules.

Eager to see these patterns for herself, Sakura decides to simulate them on her computer. However, despite her skills as a ninja and healer, coding the automaton is proving trickier than she expected. She reaches out for help, asking you to write a program that simulates an elementary cellular automaton for her.

Sakura's goal is simple: she wants to visualize the evolution of the automaton over multiple generations, starting from an initial state. This will help her uncover the beauty and complexity hidden in the seemingly straightforward rules of cellular automata. Can you help her?

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)
• ..X.. → '#' (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
...........#...........

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