Условие:
В руки учёных-шифровальщиков попал древний свиток с длинной последовательностью из n цифр (от 0 до 9). Для расшифровки тайного послания они изучают отдельные фрагменты этой последовательности.
Потенциал фрагмента с позиции l по позицию r определяется по следующему правилу:
рассматриваются все возможные пары различных позиций i и j внутри этого отрезка (1 ≤ i, j ≤ r, i ≠ j). Цифра на позиции i становится цифрой десятков, а цифра на позиции j — цифрой единиц, образуя двузначное число. Потенциал отрезка — это сумма всех таких полученных чисел.
Вам нужно помочь учёным: для заданной последовательности цифр длиной n ответить на q запросов. В каждом запросе даны границы отрезка [l, r] и требуется вычислить его потенциал.
Формат входных данных
В первой строке находится одно целое число n (1 ≤ n ≤ 100 000) — длина последовательности.
Во второй строке содержится строка s длиной n, состоящая только из цифр (от 0 до 9).
В третьей строке находится одно целое число q (1 < q < 100 000) — количество запросов.
Следующие 2 • q строк описывают запросы. В каждом запросе:
на первой строке содержится число l:
на второй строке содержится число r
Гарантируется, что 1 ≤ l ≤ r ≤ n. Позиции в последовательности нумеруются с 1.
Формат выходных данных
Для каждого запроса в отдельной строке выведите одно целое число — потенциал отрезка [l, r].
