Друзья Вася Л. и Петя П. — талантливые мальчики, которые любят писать песни собственного сочинения. В будущем они хотят стать популярными музыкантами. Ребята знают: чтобы добиться успеха, нужно регулярно тренироваться. Именно поэтому они каждый день пишут по новой песне, совершенствуя свое мастерство.

Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло $$$q$$$ вопросов про эту песню. Каждый вопрос представляет собой некоторый отрезок песни с позиции $$$l$$$ до позиции $$$r$$$ включительно. Вася рассматривает подстроку, образованную символами на этом отрезке, а затем повторяет каждую букву в этой подстроке $$$k$$$ раз, где $$$k$$$ — порядковый номер соответствующей буквы в алфавите. Например, если Вася выбрал подстроку «abbcb», то он повторит букву «a» один раз, каждую из букв «b» — по два раза, букву «c» — три раза, и полученная строка будет равна «abbbbcccbb», ее длина равна 10. Вася интересуется именно длиной полученной строки.

Помогите Пете ответить Васе на его вопросы, а именно, для каждого из заданных вопросов определите длину строки, которую выпишет Вася.

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n, q \le 1000$$$, наберут не менее $$$25$$$ баллов.

Решения, корректно работающие при $$$n, q \le 10\,000$$$, наберут не менее $$$50$$$ баллов.

Решения, корректно работающие в случае, когда $$$s$$$ состоит из символов $$$a,b$$$, наберут не менее $$$25$$$ баллов.