Substring Distinct Frequency Query

You are given a string \(S\) of length \(n\) and an integer \(q\) representing the number of queries. Each query consists of three integers \(l\), \(r\), and \(k\). The task is to extract the substring from \(S\) spanning indices \(l\) to \(r\) (1-indexed) and determine how many distinct characters in that substring appear exactly \(k\) times.

Input: The first line contains two integers \(n\) and \(q\). The second line contains the string \(S\). Each of the following \(q\) lines contains three integers \(l\), \(r\), and \(k\), describing one query.

Output: For each query, output the corresponding answer on a new line.

If no characters satisfy the condition in a query, print 0 for that query.

inputFormat

The input is given via stdin and has the following format:

n q
S
l1 r1 k1
l2 r2 k2
... 
lq rq kq

Where \(n\) is the length of the string, \(q\) is the number of queries, \(S\) is the input string, and each subsequent line defines a query with indices \(l\), \(r\) (1-indexed) and an integer \(k\).

outputFormat

The output should be printed to stdout. For each query, output a single integer on a new line representing the number of distinct characters in the substring \(S[l\ldots r]\) that occur exactly \(k\) times.

## sample

5 1
ababa
1 3 1

1

</p>