Условие:
На доске записаны N цифр. Позиции, в которых записаны цифры, занумерованы целыми положительными числами от 1 до N. Далее M раз делаются запросы следующего вида:
Выбираются два целых числа A и B (1 ≤ A ≤ B ≤ N) — параметры запроса.
Вычисляется сумма всех цифр на доске от A-й до B-й позиции включительно и записывается листе бумаги.
Все цифры от A-й до B-й включительно увеличиваются на 1 (при этом цифра `9' переходит в цифру `0'.
По заданой начальной последовательности цифр и параметрам всех запросов восстановите записи на листе бумаги.
Формат ввода
Первая строка входа содержит два целых числа N и M (1 ≤ N ≤ 2.5 ⋅ 105, 1 ≤ M ≤ 105). Вторая строка задаёт начальную последовательность цифр и состоит из N цифр. Первая цифра соответствует позиции 1, вторая — позиции 2... N-я — позиции N.
Каждая из последующих M строк содержит два целых числа A и B (1 ≤ A ≤ B ≤ N) — параметры соответствующего запроса.
Формат вывода
Выведите M строк — записанные на листе бумаги суммы в том порядке, в котором они были выписаны.
