更多假日

题目描述

给定一个由 o 和 x 组成、长度为 $N$ 的字符串 $S$,以及整数 $M$ 和 $K$。

$S$ 保证至少包含一个 x。

设 $T$ 为将 $M$ 份 $S$ 首尾拼接得到的长为 $NM$ 的字符串。 考虑把 $T$ 中恰好 $K$ 个 x 替换为 o。

你的目标是使替换后的 $T$ 中出现尽可能长的连续 o 子串。

求你能得到的连续 o 子串的最大长度。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $K$
$S$

输出格式

输出答案(一个整数)。

样例

10 1 2
ooxxooooox

9

$S=$ ooxxooooox,$T=$ ooxxooooox。

把第 3 个和第 4 个字符处的 x 替换为 o,得到 $T=$ ooooooooox。

于是我们得到一个长度为 $9$ 的连续 o 子串,这是最长的。

5 3 4
oxxox

8

$S=$ oxxox,$T=$ oxxoxoxxoxoxxox。

把第 $5,7,8$ 和第 $10$ 个字符处的 x 替换为 o,得到 $T=$ oxxooooooooxxox。

于是我们得到一个长度为 $8$ 的连续 o 子串,这是最长的。

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

19964887064

数据范围

• $N$,$M$,$K$ 均为整数。
• $1 \le N \le 3 \times 10^5$
• $1 \le M \le 10^9$
• $1 \le K \le x$,其中 $x$ 是字符串 $T$ 中 x 的个数。
• $S$ 是由 o 和 x 组成、长度为 $N$ 的字符串。
• $S$ 至少包含一个 x。