Ký tự khác nhau

Cho một xâu ký tự \(S\) gồm \(n\) chữ cái Latin in thường (a đến z).

Bạn cần xử lý \(q\) truy vấn.
Mỗi truy vấn gồm hai số nguyên \(l\) và \(r\) (\(1 \le l \le r \le n\)), yêu cầu đếm xem trong đoạn con \(S[l..r]\) có bao nhiêu ký tự khác nhau xuất hiện.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)).

• Dòng thứ hai chứa xâu \(S\) độ dài \(n\).

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số \(l, r\).

Output

Với mỗi truy vấn, in ra một số nguyên trên một dòng là số lượng ký tự khác nhau trong đoạn \([l, r]\).