有一种编程语言,其中每个程序都是“<”和“>”符号和数字的非空序列。让我们解释一下这种编程语言的解释器是如何工作的。程序通过指令指针 (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 的次数。按照输入中给出的顺序打印查询的答案。
示例
输入 #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