Hide

Problem E
Tired Terry

Terry is feeling tired and he suspects it is because of a lack of sleep. He created a device that records his sleeping pattern over a period of time measured in seconds.

Assuming that the recorded sleeping pattern keeps repeating, help Terry by letting him know how often he is tired during each of the repeating time periods.

More precisely, for integers $p$ and $d$, we say that Terry is tired at second $i$ if from second $i-p+1$ to second $i$ (inclusive) he has slept for less than $d$ seconds.

Input

The first line of input contains three integers $n$ ($1 \leq n \leq 86\, 400$), the length of Terry’s sleep pattern, $p$ ($1 \leq p \leq n$), and $d$ ($1 \leq d \leq p$) as described above.

The second line of input contains a single string of length $n$ which describes the period of time that is recorded. The $i^\textrm {th}$ such character is a W if Terry is awake at the $i^\textrm {th}$ second, or is a Z if Terry is asleep at the $i^\textrm {th}$ second.

Output

Display a single integer which represents the number of seconds that Terry is tired during each of the repeating time periods.

Sample Input 1 Sample Output 1
2 1 1
WZ
1
Sample Input 2 Sample Output 2
5 3 2
WZWWZ
4

Please log in to submit a solution to this problem

Log in