Hide

Problem D
Rule N

/problems/rulen/file/statement/en/img-0001.png
$300$ iterations of Rule $90$ applied to an initial state where exactly one cell is initially set to $1$. Image retrieved from Wikipedia: Rule 90, CC BY-SA 4.0

A cellular automaton is an infinite one-dimensional array of cells. Each cell in the array has one of two states, $0$ or $1$, but the state of the cell may change over the course of an iterative process. At each iteration, each cell will take on a new state by applying a transition rule that operates on the state of the cell and the state of its two neighbouring cells. The state of a cell and its two neighbours is called a “pattern.” Observe that there are eight possible patterns: $111$, $110$, $101$, $100$, $011$, $010$, $001$, and $000$.

The transition rule is specified by a nonnegative integer, $N$, less than $256$. The indices of the nonzero digits of the $8\textrm{-bit}$ binary representation of $N$ specify which patterns will result in a cell having $1$ as its new state after applying the transition rule. Conversely, the indices of the zero digits in the $8\textrm{-bit}$ binary representation of $N$ (including leading zeroes) specify which patterns will result in a cell having $0$ as its new state after applying the transition rule. In particular, the least significant digit of the $8\textrm{-bit}$ binary representation of $N$ defines the new state for the pattern $000$, the second least significant digit defines the new state for the pattern $001$, the third least significant digit defines the new state for the pattern $010$, etc.

For example, Rule $158$ (where $158=10011110_2$) has the following transitions.

Pattern

$111$

$110$

$101$

$100$

$011$

$010$

$001$

$000$

Next State

$1$

$0$

$0$

$1$

$1$

$1$

$1$

$0$

When a transition rule is applied, it is applied to all cells simultaneously and the state changes are instantaneous.

Given a rule, $N$, a number of iterations, $R$, and the current states of a contiguous section of $L$ cells of a cellular automaton, compute the states of the cells in that section in each of the next $R$ iterations of the transition rule being applied. It is assumed that each of the infinitely many cells in the cellular automaton that are not in the given section are initially in the $0$ state.

Input

The input consists of two lines. The first line consists of three integers, $N$, $L$, and $R$, where $0\leq N \leq 255$, $1\leq L \leq 100$, and $1\leq R \leq 100$. The next line is a sequence of $L$ binary digits giving the initial states of the section of cells in the cellular automaton.

Output

Output $R$ lines, representing the states of the cells in the given section of the cellular automaton in each of the first $R$ iterations of applying transition rule $N$.

Sample Input 1 Sample Output 1
158 7 6
1101000
1001100
0111010
0110011
1101110
1001100
0111011
Sample Input 2 Sample Output 2
90 51 32
000000000000000000000000010000000000000000000000000
000000000000000000000000101000000000000000000000000
000000000000000000000001000100000000000000000000000
000000000000000000000010101010000000000000000000000
000000000000000000000100000001000000000000000000000
000000000000000000001010000010100000000000000000000
000000000000000000010001000100010000000000000000000
000000000000000000101010101010101000000000000000000
000000000000000001000000000000000100000000000000000
000000000000000010100000000000001010000000000000000
000000000000000100010000000000010001000000000000000
000000000000001010101000000000101010100000000000000
000000000000010000000100000001000000010000000000000
000000000000101000001010000010100000101000000000000
000000000001000100010001000100010001000100000000000
000000000010101010101010101010101010101010000000000
000000000100000000000000000000000000000001000000000
000000001010000000000000000000000000000010100000000
000000010001000000000000000000000000000100010000000
000000101010100000000000000000000000001010101000000
000001000000010000000000000000000000010000000100000
000010100000101000000000000000000000101000001010000
000100010001000100000000000000000001000100010001000
001010101010101010000000000000000010101010101010100
010000000000000001000000000000000100000000000000010
101000000000000010100000000000001010000000000000101
000100000000000100010000000000010001000000000001000
101010000000001010101000000000101010100000000010101
000001000000010000000100000001000000010000000100000
000010100000101000001010000010100000101000001010000
000100010001000100010001000100010001000100010001000
101010101010101010101010101010101010101010101010101
000000000000000000000000000000000000000000000000000

Please log in to submit a solution to this problem

Log in