## Problem C. Compression research ≡

• problems
 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

Many compression algorithms are based on finding frequently repeating substrings in the input data. Since it is often impractical to search the whole input for repetitions, only a limited compression window is considered on each step.

While researching a new compression algorithm, young computer scientist Vasya encountered the following problem.

Given input string of N bits, let the compression window be any substring of M bits. Inside each compression window, find the maximum number of occurrences of any substring of length L (L ≤ M).

In the sample input 1 below, compression window length is equal to string length, so there is only a single window. Most frequent substring of length 2 is 01, which occurs 5 times.

### Input file format

First line of input file contains integers L M. Second line input file contains a string of length N, each character either 0 or 1.

### Output file format

Output file must contain N − M + 1 integers — maximum substring frequencies for each compression window.

### Constraints

1 ≤ M ≤ N ≤ 2 × 105, 1 ≤ L ≤ 100

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 10
0101010101

5


2
1 3
1110000

3 2 2 3 3 

0.096s 0.010s 13