You are given a string of length KaTeX can only parse string typed expression. You need to process KaTeX can only parse string typed expression queries. Each query consists of a range KaTeX can only parse string typed expression and KaTeX can only parse string typed expression (0-based indices) and a character KaTeX can only parse string typed expression.
For each query, consider only the substring from index KaTeX can only parse string typed expression to KaTeX can only parse string typed expression (inclusive). Among all occurrences of character KaTeX can only parse string typed expression within this range, determine the index of the middle occurrence.
If the number of occurrences within the range is odd, print the index of the exact middle occurrence.
If the number of occurrences within the range is even, print the index of the first middle occurrence.
If the character does not appear in the given range, print KaTeX can only parse string typed expression.
The second line contains the string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression consisting of lowercase English letters.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression and a character KaTeX can only parse string typed expression — representing a query.
9 3
abacabacc
0 8 a
2 6 b
3 8 c
Output
2
5
7
Explanation
Query 1: range [0, 8], character 'a'
Positions of 'a' in this range: (0, 2, 4, 6).
Total = 4 (even), middle positions are 2 and 4.
First middle occurrence index = 2.
Query 2: range [2, 6], character 'b'
Positions of 'b' in this range: (5).
Total = 1 (odd), middle occurrence index = 5.
Query 3: range [3, 8], character 'c'
Positions of 'c' in this range: (3, 7, 8).
Total = 3 (odd), middle occurrence index = 7.