Tape Programming

题意翻译

有一种编程语言，在这种语言下一个程序可以用由数字、$<$ 和 $>$ 组成的字串表示。程序运行时有一个指针，移动方向向右。 我们重复以下操作直到指针移动到字串外。 * 如果指针指向一个数字，则输出这个数字并将数字减 $1$。如果输出的数字为 $0$，则将它从字串中删除。 * 如果指针指向 $<$ 或 $>$，则改变移动方向，并以这个方向移动一格。若为 $<$ 则移动方向向左，若为 $>$ 则移动方向向右。若移动后指针仍然指向 $<$ 或 $>$，则将移动前指向的字符删除。 对于给出的长度为 $n$ 的字串，有 $q$ 组询问，每次询问子串 $[l,r]$ 作为一段程序时，每个数字的输出次数为多少。

题目描述

There is a programming language in which every program is a non-empty sequence of "<" and ">" signs and digits. Let's explain how the interpreter of this programming language works. A program is interpreted using movement of instruction pointer (IP) which consists of two parts. - Current character pointer (CP); - Direction pointer (DP) which can point left or right; Initially CP points to the leftmost character of the sequence and DP points to the right. We repeat the following steps until the first moment that CP points to somewhere outside the sequence. - If CP is pointing to a digit the interpreter prints that digit then CP moves one step according to the direction of DP. After that the value of the printed digit in the sequence decreases by one. If the printed digit was $ 0 $ then it cannot be decreased therefore it's erased from the sequence and the length of the sequence decreases by one. - If CP is pointing to "<" or ">" then the direction of DP changes to "left" or "right" correspondingly. Then CP moves one step according to DP. If the new character that CP is pointing to is "<" or ">" then the previous character will be erased from the sequence. If at any moment the CP goes outside of the sequence the execution is terminated. It's obvious the every program in this language terminates after some steps. We have a sequence $ s_{1},s_{2},...,s_{n} $ of "<", ">" and digits. You should answer $ q $ queries. Each query gives you $ l $ and $ r $ and asks how many of each digit will be printed if we run the sequence $ s_{l},s_{l+1},...,s_{r} $ as an independent program in this language.

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ q $ $ (1<=n,q<=10^{5}) $ — represents the length of the sequence $ s $ and the number of queries. The second line contains $ s $ , a sequence of "<", ">" and digits (0..9) written from left to right. Note, that the characters of $ s $ are not separated with spaces. The next $ q $ lines each contains two integers $ l_{i} $ and $ r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ — the $ i $ -th query.

输出格式

For each query print $ 10 $ space separated integers: $ x_{0},x_{1},...,x_{9} $ where $ x_{i} $ equals the number of times the interpreter prints $ i $ while running the corresponding program. Print answers to the queries in the order they are given in input.

输入输出样例

输入样例 #1

7 4
1>3>22<
1 3
4 7
7 7
1 7

输出样例 #1

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

题意翻译

有一种编程语言，在这种语言下一个程序可以用由数字、$<$ 和 $>$ 组成的字串表示。程序运行时有一个指针，移动方向向右。 我们重复以下操作直到指针移动到字串外。 * 如果指针指向一个数字，则输出这个数字并将数字减 $1$。如果输出的数字为 $0$，则将它从字串中删除。 * 如果指针指向 $<$ 或 $>$，则改变移动方向，并以这个方向移动一格。若为 $<$ 则移动方向向左，若为 $>$ 则移动方向向右。若移动后指针仍然指向 $<$ 或 $>$，则将移动前指向的字符删除。 对于给出的长度为 $n$ 的字串，有 $q$ 组询问，每次询问子串 $[l,r]$ 作为一段程序时，每个数字的输出次数为多少。