Giả sử chúng ta đánh số các chữ cái từ \(a\) đến \(z\) có số thứ tự lần lượt là \(1,2,...,26\).
Bây giờ, An có một xâu \(s\) gồm \(n\) chữ cái in thường(xâu được đánh số từ \(1\) đến \(n\)) và có \(q\) truy vấn mà An cần bạn giúp đỡ, mỗi truy vấn gồm hai chỉ số \(l,r(1\le l\le r\le n)\) và định nghĩa truy vấn cụ thể như sau:

++ Đầu tiên, ta chọn ra xâu con \(s[l..r]\) gồm các chữ cái liên tiếp từ \(l\) đến \(r\) trong xâu \(s\)

++ Tiếp theo biến đối xâu con này thành xâu \(t\) và in ra độ dài xâu \(t\) ra màn hình với xâu \(t\) được tạo ra bằng cách như sau:

\(\implies\) s[l] được lặp lại đúng bằng số thứ tự của \(s[l]\) trong bảng chữ cái alphabet, tương tự đến \(s[l+1],s[l+2],...,s[r]\)

Ví dụ 1: \(s='abdcaba'\) và ta có 2 truy vấn

• Truy vấn 1: \(1\text{ }3\). Khi đó: \(s[1..3]=abd\)
  \(\implies\) Kết quả thu được là: \(t=\underbrace{a}_{\text{1 lần}}\underbrace{bb}_{\text{2 lần}}\underbrace{dddd}_{\text{4 lần}}\).
  Và độ dài của xâu \(t\) là \(7\)
• Truy vấn 2: \(3\text{ }4\). Khi đó: \(s[3..4]=dc\)
  \(\implies\) Kết quả thu được là: \(t=\underbrace{dddd}_{\text{4 lần}}\underbrace{ccc}_{\text{3 lần}}\). Và độ dài của xâu \(t\) là \(7\)

Input

• Dòng đầu tiên chứa số nguyên dương \(n,q(1\le n,q\le 100000)\)
• Dòng tiếp theo chứa xâu \(s\) có độ dài \(n\)
• \(q\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên dương \(l,r(1\le l\le r\le n)\)

Output

• Ứng với mỗi truy vấn, hãy in kết quả ra màn hình.

Example

7 2
abdcaba
1 3
3 4

7
7