Codeforces Round 148 (Div. 2) |
---|
Закончено |
Существует язык программирования, в котором каждая программа представлена непустой последовательностью символов «<» и «>» и цифр. Объясним, как работает интерпретатор этого языка программирования. Программа интерпретируется посредством движения указателя команды (IP), который состоит из двух частей.
Изначально CP указывает на крайний левый символ в последовательности, а DP указывает направо.
Мы повторяем следующие шаги до тех пор, пока CP впервые укажет куда-то за пределы последовательности.
Если в какой-то момент выполнения программы CP выходит за пределы последовательности, то выполнение программы завершается.
Очевидно, что любая программа на этом языке завершается после некоторого количества шагов.
У Вас есть последовательность s1, s2, ..., sn, состоящая из символов «<», «>» и чисел. Вы должны ответить на q запросов. Каждый запрос характеризуется двумя целыми числами l и r и спрашивает, сколько раз будет выведена каждая цифра, если мы запустим последовательность sl, sl + 1, ..., sr как независимую программу на описанном языке.
В первой строке входных данных содержатся два целых числа n и q (1 ≤ n, q ≤ 100) — длина последовательности s и количество запросов.
Вторая строка содержит s, последовательность из «<», «>» и цифр (0..9), записанных слева направо. Заметьте, что символы s не разделяются пробелами.
Каждая из следующих q строк содержит по два целых числа li и ri (1 ≤ li ≤ ri ≤ n) — i-ый запрос.
Для каждого запроса выведите 10 целых чисел, записанных через пробел: x0, x1, ..., x9, где xi равняется количеству выведенных цифр i при выполнении соответствующей программы из запроса. Выводите ответы на запросы в том порядке, в каком запросы даны во входных данных.
7 4
1>3>22<
1 3
4 7
7 7
1 7
0 1 0 1 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
2 3 2 1 0 0 0 0 0 0
Название |
---|