B. Простое Ленточное Программирование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

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

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

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