CF239B.Easy Tape Programming

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.

存在一种编程语言，其中每个程序都是一个非空的由字符 <、> 和数字组成的序列。下面解释该编程语言解释器的工作方式。程序的执行依赖于指令指针（IP）的移动，而指令指针由两部分组成：

• 当前字符指针（CP）；
• 方向指针（DP），其方向可为向左或向右；

初始时，CP 指向序列最左侧的字符，DP 指向右。

我们重复执行以下步骤，直到 CP 首次指向序列之外的位置为止：

• 若 CP 指向一个数字，则解释器输出该数字，然后 CP 沿 DP 所指方向移动一步。此后，序列中该被输出数字的值减 1。若被输出的数字为 0，则无法再减小，因此该 0 将从序列中删除，序列长度减 1。
• 若 CP 指向 < 或 >，则 DP 的方向相应地变为“向左”或“向右”。随后 CP 沿 DP 所指方向移动一步。若 CP 移动后所指向的新字符是 < 或 >，则原 CP 所指的字符（即移动前的字符）将从序列中删除。

若在任意时刻 CP 超出序列范围，则执行终止。

显然，该语言中的每个程序均会在有限步后终止。

现给定一个由 <、> 和数字组成的序列 $ s_1, s_2, \dots, s_n $。你需要回答 $ q $ 个查询。每个查询给出 $ l $ 和 $ r $，要求你计算：若将子序列 $ s_l, s_{l+1}, \dots, s_r $ 作为独立程序运行，最终共输出多少个 0、1、…、9。

The first line of input contains two integers n and q (1 ≤ n, q ≤ 100) — 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.

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 100$），分别表示序列 $s$ 的长度以及查询的个数。

第二行包含序列 $s$，其由字符 <、> 和数字（0 到 9）从左到右依次组成。注意：$s$ 中的字符之间不包含空格。

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 个查询。

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.

对于每个查询，输出 10 个以空格分隔的整数：$x_0,\ x_1,\ \dots,\ x_9$，其中 $x_i$ 表示解释器在运行对应程序时打印数字 $i$ 的次数。请按照输入中查询给出的顺序输出各查询的答案。