P7180 [BalticOI 2004] Repeats (Day2)

If a string $s$ satisfies: - For a pair of numbers $(k,l)~(k\ge 1,l\ge 1)$. - $s$ is formed by concatenating $k$ copies of a string $t$ of length $l$. Then $s$ is called a $(k,l)\text{ - repeat}$ string. For example, $s=\tt abaabaabaaba$ is a $(4,3)\text{ - repeat}$ string with $t=\tt aba$. Given a string $u$ (containing only characters $\texttt a$ and $\texttt b$), you need to find a **contiguous** substring of $u$ that is a $(k,l)\text{ - repeat}$ string, such that $k$ is as large as possible. For example, $u=\tt babb\underline{abaabaabaaba}b$, where the underlined part is a $(4,3)\text{ - repeat}$ string, and in this case $k$ is maximized.

The first line contains an integer $n$, representing the length of $u$. The next $n$ lines each contain one character ($\texttt a$ or $\texttt b$), describing the string.

The first line contains a number $k$. The second line contains a number $l$. The third line contains a number $p$, representing the starting position of this $(k,l)\text{ - repeat}$ substring (positions start from $1$). **If there are multiple valid answers, output any one of them.**

#### Constraints For $100\%$ of the testdata, $1\le n\le 5\times 10^{4}$, $u_i\in\{\tt a,b\}$. #### Notes Translated from [BalticOI 2004 Day2 A Repeats](https://boi.cses.fi/files/boi2004_day2.pdf). Special thanks to @[Sprague_Garundy](https://www.luogu.com.cn/user/764746) for providing the SPJ. Translated by ChatGPT 5