题目描述

Petya 曾经写过一首悲伤的情歌，并把它分享给了 Vasya。这首歌是一个只包含小写英文字母的字符串。Vasya 针对这首歌提出了** q 个问题。每个问题都涉及到歌曲的一个子区间，从第 l 个字母到第 r个字母。Vasya 会取出该区间对应的子串，并将子串中的每个字母重复 k 次，其中 k 是该字母在英文字母表中的序号。例如，如果问题涉及的子串是 "abbcb"，那么 Vasya 会将字母 'a' 重复 1 次，每个字母 'b' 重复 2 次，字母 'c' 重复 3 次，得到的新字符串为 "abbbbcccbb"，其长度为 **10。Vasya 想知道每次得到的新字符串的长度。

请帮助 Petya 计算 Vasya 得到的每个字符串的长度。

输入格式

第一行包含两个整数** n 和 q（1≤n≤100000，1≤q≤100**000），分别表示歌曲的长度和问题的数量。

第二行包含一个字符串** s，表示歌曲，由 n **个小写英文字母组成。

接下来的** q 行，每行包含两个整数 l 和 r（1≤l≤r≤n**），表示每个问题的区间。

输出格式

输出** q **行，对于每个问题，输出 Vasya 得到的新字符串的长度。 输入

7 3 abacaba 1 3 2 5 1 7 输出 4 7 11