Rich Substrings

A string with length $L$ is called *rich* if $L \ge 3$ and there is a character which occurs in this string strictly more than $L/2$ times. You are given a string $S$ and you should answer $Q$ queries on this string. In each query, you are given a substring $S_L, S_{L+1}, \ldots, S_R$. Consider all substrings of this substring. You have to determine whether at least one of them is rich. ###