На доске записаны N цифр. Позиции, в которых записаны цифры, занумерованы целыми положительными числами от 1 до N. Далее M раз делаются запросы следующего вида: 1. Выбираются два целых числа A и B (1 ≤ A ≤ B ≤ N) — параметры запроса. 2. Вычисляется сумма

На доске записаны 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 строк — записанные на листе бумаги суммы в том порядке, в котором они были выписаны.

Пример 1
Ввод Вывод
4 3
1234
1 4
1 4
1 4
10
14
18
Пример 2
Ввод Вывод
4 4
1234
1 1
1 2
1 3
1 4
1
4
9
16
Пример 3
Ввод Вывод
7 5
9081337
1 3
3 7
1 3
3 7
1 3
17
23
1
19
5 на с++