Задача . D. Ленточное Программирование

Существует язык программирования, в котором каждая программа представлена непустой последовательностью символов «<» и «>» и цифр. Объясним, как работает интерпретатор этого языка программирования. Программа интерпретируется посредством движения указателя команды (IP), который состоит из двух частей.

• Указатель текущего символа (CP);
• Указатель направления (DP), который может указывать налево или направо;

Изначально CP указывает на крайний левый символ в последовательности, а DP указывает направо.

Мы повторяем следующие шаги до тех пор, пока CP впервые укажет куда-то за пределы последовательности.

• Если CP указывает на цифру, то интерпретатор выводит эту цифру. Затем CP перемещается на один шаг согласно направлению DP. После этого значение написанной в последовательности цифры уменьшается на один. Если выведенная цифра была 0, значит, ее нельзя уменьшить. Поэтому она удаляется из последовательности, и длина последовательности уменьшается на один.
• Если CP указывает на «<» или «>», то направление DP меняется на «влево» или «вправо», соответственно. Затем CP двигается на один шаг согласно DP. Если новый символ, на который указывает CP — это «<» или «>», то предыдущий символ будет удален из последовательности.

Если в какой-то момент выполнения программы CP выходит за пределы последовательности, то выполнение программы завершается.

Очевидно, что любая программа на этом языке завершается после некоторого количества шагов.

У Вас есть последовательность s₁, s₂, ..., s_n, состоящая из символов «<», «>» и чисел. Вы должны ответить на q запросов. Каждый запрос характеризуется двумя целыми числами l и r и спрашивает, сколько раз будет выведена каждая цифра, если мы запустим последовательность s_l, s_l + 1, ..., s_r как независимую программу на описанном языке.