Fishing

Time limit1sMemory limit1024 MB

Summary

Find the starting day among the first N days whose window of k consecutive days contains the most rainy days, choosing the smallest index on a tie.

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

Problem

Martynas is planning a fishing trip and wants to spend $k$ days fishing. Since fish bite best on rainy days, he wants to choose $k$ consecutive days that contain as many rainy days as possible.

Input

The first line contains two integers $N$ and $k$ : $N$ is the number of days on which the trip may start, and $k$ is how many consecutive days the trip lasts.

The second line gives the weather forecast for $N + k - 1$ days as a string of characters $c_i$ ( $1 \le i \le N + k - 1$ ):

L — day $i$ is rainy;
S — day $i$ is sunny.

Output

Output a single number — the day on which the trip begins. Martynas wants to leave as early as possible, so if several starting days give the maximum number of rainy days, output the smallest one. (The answer is between $1$ and $N$ .)

Constraints

$1 \le k, N \le 1\,000\,000$ .

Examples1

Example 1
Input
```
10 4
SSSLSLSLSSSSS
```
Expected output
```
3
```