Задача A. Новогодняя игра ≡

Условие

В Новогоднюю ночь Дед Мороз предложил Тимофею и Насте игру на сообразительность, прежде чем вручить подарки. В этой игре Дед Мороз произнесет два числа — a и b, и Тимофей должен записать все числа от a до b в возрастающем порядке. Затем Настя пронумерует каждую цифру в получившейся строке, чтобы подготовиться к вопросам.

Дед Мороз задаст k вопросов, каждый из которых будет состоять из двух чисел — l и r, где l и r — это будут индексы записанных цифр. Для каждого запроса нужно будет подсчитать и вывести сумму цифр на отрезке от l до r.

Напишите программу, которая поможет ребятам правильно ответить на вопросы и получить подарки.

Формат входных данных

В первой строке входных данных подается два числа - a и b (1 <  = a < b <  = 10⁵).

Во второй строке подается k (1 <  = k <  = 10⁵) - количество вопросов, которые задает Настя.

В следующих строках входных данных дается k запросов, состоящих из двух чисел l и r (1 <  = l < r <  =  длины строки), где l и r — индексы цифр.

Формат выходных данных

Для каждого k_i запроса необходимо вывести единственный ответ - сумму цифр на отрезке от l до r.

Решения, работающие при b < 100 будут набирать не более 20 баллов.

Решения, работающие при b < 10³ будут набирать не более 40 баллов.

Решения, работающие при b < 10⁴ будут набирать не более 70 баллов.

Решения, работающие при b <  = 10⁵ будут набирать не более 100 баллов.

Примеры тестов

1 10
3
2 5
5 8
1 10

14
26
46