Election

This problem is translated from BalkanOI 2018 Day1 T1 "Election".

You are given a string \(S[1\dots N]\) of length \(N\) consisting only of the characters C and T. There are \(Q\) queries. In each query you are given two integers \(L\) and \(R\); let \(S' = S[L\dots R]\) be the corresponding substring. Your task is to determine the minimum number of characters you must delete from \(S'\) so that the remaining string \(A\) satisfies the following condition:

[ \text{For every prefix } P \text{ of } A,; #C(P) \ge #T(P) \quad \text{and} \quad \text{for every suffix } Q \text{ of } A,; #C(Q) \ge #T(Q). ]

It can be proved that an answer always exists (deleting all characters always gives an empty string that vacuously satisfies the condition). In other words, if you can choose a subsequence of \(S'\) (preserving the original order) that satisfies the condition and has maximum possible length \(L^*\), then you must output \(|S'| - L^*\).

Note on the condition: If we interpret character C as "+1" and T as "-1", then the condition requires that for every prefix the partial sum is nonnegative, and for every suffix it is also nonnegative. Equivalently, if the selected subsequence \(A\) has final difference \(d = \#C(A) - \#T(A)\), then every prefix sum must lie in the interval \([0, d]\). One may show that any subsequence \(A\) satisfying this property can always be decomposed as \(A = U \; V\) where \(U\) is a balanced subsequence (with difference 0 when interpreted as parentheses) and \(V\) is a (possibly empty) sequence of the letter C (ensuring that the overall last character is C).

inputFormat

The input begins with a line containing two integers \(N\) and \(Q\) \((1 \le N, Q \le \text{small constraints})\), where \(N\) is the length of the string and \(Q\) is the number of queries.

The next line contains a string \(S\) of length \(N\) consisting only of the characters C and T.

Then \(Q\) lines follow, each containing two integers \(L\) and \(R\) (\(1 \le L \le R \le N\)). For each query, consider \(S' = S[L\dots R]\).

outputFormat

For each query, output one integer on a separate line: the minimum number of deletions required so that, after deleting that many characters from \(S'\), the remaining subsequence satisfies that for every prefix and every suffix the number of C's is at least the number of T's.

sample

5 3
CCTCT
1 5
2 4
3 5

1
0
2