Unique Characters in Substrings

You are given a string s of length n consisting of lowercase English letters. Your task is to answer q queries. In each query, you will be given two integers \(l\) and \(r\) (1-indexed) and you need to determine the number of unique characters in the substring \(s[l\ldots r]\).

Input Format: The first line contains two integers \(n\) and \(q\), denoting the length of the string and the number of queries respectively. The second line contains the string \(s\). This is followed by \(q\) lines, each containing two integers \(l\) and \(r\) representing a query.

Output Format: For each query, output a single line containing the number of unique characters in the specified substring.

Example:

Input:
10 3
abcabcabcx
1 3
2 6
1 10
Output:
3
3
4

</p>

inputFormat

The input consists of multiple lines:

• The first line contains two integers \(n\) and \(q\) separated by a space, where \(n\) is the length of the string and \(q\) is the number of queries.
• The second line contains the string \(s\) of length \(n\), consisting only of lowercase English letters.
• The following \(q\) lines each contain two integers \(l\) and \(r\) (1-indexed) separated by a space, representing a query asking for the number of unique characters in the substring \(s[l\ldots r]\).

outputFormat

For each query, output on a new line a single integer representing the number of unique characters in the corresponding substring of \(s\).

## sample

10 3
abcabcabcx
1 3
2 6
1 10

3
3
4

</p>