Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Binary Witch
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1578Accepted: 581

Description

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 a1, a2, ..., aN be the sequence of binary digits, where ai = 0 indicates that i-th day was rainy, and ai = 1 -- that it was sunny. To predict the weather in day N+1, consider the t-postfix aN-t+1, aN-t+2, ..., aN 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 ak = aN-t+1, ak+1 = aN-t+2, ..., ak+t-1 = aN then the predicted value will be ak+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 aN+1 = b.

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

Input

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

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

Sample Input

10 7
1101110010

Sample Output

0100100

Source

Northeastern Europe 2000, Far-Eastern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator