Tired Terry

Interview

Time limit1sMemory limit512 MB

Summary

Given a circular sleep pattern of length n, count for how many seconds i the preceding p seconds contain fewer than d seconds of sleep.

Level: Medium4 of 10
Topics: Sliding window, Prefix sum, Array, Implementation
Solved: No attempts yet

Problem

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 \le n \le 86\,400$ ), the length of Terry's sleep pattern, $p$ ( $1 \le p \le n$ ), and $d$ ( $1 \le d \le 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$ th such character is a W if Terry is awake at the $i$ th second, or is a Z if Terry is asleep at the $i$ th second.

Output

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

Examples2

Example 1
Input
```
2 1 1
WZ
```
Expected output
```
1
```
Example 2
Input
```
5 3 2
WZWWZ
```
Expected output
```
4
```