Задача . C. Конфеты!

Рассмотрим последовательность цифр длины \(2^k\) \([a_1, a_2, \ldots, a_{2^k}]\). Будем выполнять с ней следующую операцию: заменить пару \((a_{2i+1}, a_{2i+2})\) на \((a_{2i+1} + a_{2i+2})\bmod 10\) для \(0\le i<2^{k-1}\). За каждое \(i\) такое, что \(a_{2i+1} + a_{2i+2}\ge 10\), мы получаем конфету! В результате, мы получим последовательность цифр длины \(2^{k-1}\).

Менее формально, последовательность длины \(2^k\) мы разбиваем на \(2^{k-1}\) пар, каждая из которых состоит из двух чисел: первая пара состоит из первых двух чисел, вторая из третьего и четвертого, \(\ldots\), последняя пара состоит из (\(2^k-1\))-го и (\(2^k\))-го чисел. За каждую пару, сумма чисел в которой не менее \(10\), мы получаем конфету. После этого, мы заменяем каждую пару чисел на остаток от деления их суммы на \(10\) (при этом сохраняем порядок чисел).

Будем выполнять данную операцию с последовательностью, пока она не станет длины \(1\). Пусть \(f([a_1, a_2, \ldots, a_{2^k}])\) обозначает количество конфет, которые мы получим в процессе.

К примеру: если изначальной последовательностью была \([8, 7, 3, 1, 7, 0, 9, 4]\), то:

После первой операции последовательность станет \([(8 + 7)\bmod 10, (3 + 1)\bmod 10, (7 + 0)\bmod 10, (9 + 4)\bmod 10]\) \(=\) \([5, 4, 7, 3]\), и мы получим \(2\) конфеты так как \(8 + 7 \ge 10\) и \(9 + 4 \ge 10\).

После второй операции последовательность станет \([(5 + 4)\bmod 10, (7 + 3)\bmod 10]\) \(=\) \([9, 0]\), и мы получим еще одну конфету так как \(7 + 3 \ge 10\).

После последней операции последовательность станет \([(9 + 0) \bmod 10]\) \(=\) \([9]\).

Следовательно, \(f([8, 7, 3, 1, 7, 0, 9, 4]) = 3\), так как мы получили всего \(3\) конфеты.

Вам дана последовательность цифр длины \(n\) \(s_1, s_2, \ldots s_n\). Вы должны ответить на \(q\) запросов вида \((l_i, r_i)\), где для \(i\)-го запроса вы должны вывести \(f([s_{l_i}, s_{l_i+1}, \ldots, s_{r_i}])\). Гарантируется, что \(r_i-l_i+1\) имеет вид \(2^k\) для некоторого неотрицательного целого \(k\).