7864번 - Binary Witch 다국어

Once upon a time in the silent depths of digital forests there lived a Binary Witch. She was able to forecast weather, telling for any day in the future whether it will be rainy or sunny.

Her magic was based on the following ancient rule: let a₁, a₂, ..., a_N be the sequence of binary digits, where a_i = 0 indicates that i-th day was rainy, and a_i = 1  that it was sunny. To predict the weather in day N + 1, consider the t-postfix a_N-t+1, a_N-t+2, ..., a_N consisting of the last t elements. If that postfix is encountered somewhere before the position N - t + 1, i.e. if there is such k ≤ N - t, that a_k= a_N-t+1, a_k+1 = a_N-t+2, ..., a_k+t-1 = a_N then the predicted value will be a_k+t.

If there is more than one occurrence of t-postfix, then the rightmost one (with maximal k) will be taken. So, to make a prediction, she tried t-postfixes, consequently for t = 13, 12, ..., 1, stopping after the first prediction. If neither postfix was found, she predicted rain (0). If prediction for more than one day is needed, it is assumed that all previous days are predicted correctly, so if first predicted value is b, then we make forecast for day N + 2 based on N + 1 values, where a_N+1 = b.

Because the witch was burned long ago, your task is to write a program to perform her arcane job.

First line of input file contains two integers N (1 ≤ N ≤ 1000000) and L (1 ≤ L ≤ 1000), separated by space. Second line contains a string of N characters 0 and 1.

Output file must contain a single string of L characters, which are forecasts for days N + 1, N + 2, ..., N + L.