Question
Middle Occurrence Query
You are given a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression and KaTeX can only parse string typed expression queries. Each query contains a character.
For each query, determine the index of the middle occurrence of that character in the string.
-
If the total number of occurrences of that character is odd, return the index of the exact middle occurrence.
-
If the total number of occurrences is even, return the index of the first middle occurrence.
-
If the character does not appear in the string, print KaTeX can only parse string typed expression.
All indices are considered 0-based.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the length of the string and the number of queries.
The second line contains the string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
The next KaTeX can only parse string typed expression lines each contain a single character — the query character.
The second line contains the string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
The next KaTeX can only parse string typed expression lines each contain a single character — the query character.
Output
For each query, in a new line, print a single integer — the index of the required middle occurrence (0-based), or KaTeX can only parse string typed expression if the character does not appear in the string.
Example
Input
9 3
abacabacc
a
b
c
Output
2
1
7
Explanation
For character KaTeX can only parse string typed expression: positions are (0, 2, 4, 6). Total occurrences = 4 (even), so the two middle positions are 2 and 4. The first middle occurrence is index 2.
For character KaTeX can only parse string typed expression: positions are (1, 5). Total = 2 (even), first middle is index 1.
For character KaTeX can only parse string typed expression: positions are (3, 7, 8). Total = 1 (odd), middle is index 7.
9 3
abacabacc
a
b
c
Output
2
1
7
Explanation
For character KaTeX can only parse string typed expression: positions are (0, 2, 4, 6). Total occurrences = 4 (even), so the two middle positions are 2 and 4. The first middle occurrence is index 2.
For character KaTeX can only parse string typed expression: positions are (1, 5). Total = 2 (even), first middle is index 1.
For character KaTeX can only parse string typed expression: positions are (3, 7, 8). Total = 1 (odd), middle is index 7.