Binary Witch

Long ago, in the silent depths of the digital forest, there lived a Binary Witch. She could forecast the weather, telling for any future day whether it would be rainy ($0$) or sunny ($1$).

Her magic followed this ancient rule. Let $a_1, a_2, \ldots, a_N$ be a sequence of binary digits, where $a_i = 0$ means day $i$ was rainy and $a_i = 1$ means it was sunny. To predict the weather on day $N+1$, look at the $t$-postfix $a_{N-t+1}, a_{N-t+2}, \ldots, a_N$ made of the last $t$ elements. If this postfix also occurs somewhere before position $N-t+1$ — that is, if there exists $k \le N-t$ with $a_k = a_{N-t+1},\ a_{k+1} = a_{N-t+2},\ \ldots,\ a_{k+t-1} = a_N$ — then the predicted value is $a_{k+t}$.

If the $t$-postfix occurs more than once, take the rightmost occurrence, the one with the largest $k$. To make a prediction she tries the $t$-postfixes in order $t = 13, 12, \ldots, 1$ and stops as soon as a prediction is produced. If no postfix is found, she predicts rain ($0$). When more than one day must be forecast, every previously predicted day is assumed correct: if the first predicted value is $b$, set $a_{N+1} = b$, forecast day $N+2$ from the $N+1$ values, and so on.

Write a program that performs the witch's task.

The first line contains two integers $N$ ($1 \le N \le 10^6$) and $L$ ($1 \le L \le 1000$), separated by a space. The second line contains a string of $N$ characters, each $0$ or $1$.

Print a single string of $L$ characters: the forecasts for days $N+1, N+2, \ldots, N+L$.