Problem: 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 s1, s2, ..., sn 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 sl, sl + 1, ..., sr as an independent program in this language.

Input

The first line of input contains two integers n and q (1 ≤ n, q ≤ 105) — 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 li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output

For each query print 10 space separated integers: x0, x1, ..., x9 where xi 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.

Examples

Input

7 4
1&gt;3&gt;22&lt;
1 3
4 7
7 7
1 7


Output

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

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Solution {
    private IO io;
    private int ioMode = -1;
    private String problemName = "";
    private final String mjArgument = "master_j";

    public static void main(String programArguments[]) throws IOException{
        if(programArguments != null && programArguments.length > 0)
            new Solution().run(programArguments[0]);
        else
            new Solution().run(null);
    }

    private void run(String programArgument) throws IOException {
//         _______________________________________________ _________
//        |   Input Mode     |      Output Mode    | mode | comment |
//        |------------------|---------------------|----- |---------|
//        |   input.txt      |      System.out     |  0   |    mj   |
//        |   System.in      |      System.out     |  1   |  T / CF |
//        |<problemName>.in  |  <problemName>.out  |  2   |         |
//        |   input.txt      |      output.txt     |  3   |    C    |
//        |__________________|_____________________|______|_________|
        long nanoTime = 0;
        if(programArgument != null && programArgument.equals(mjArgument)) // mj
            ioMode = 0;
        else if(System.getProperty("ONLINE_JUDGE") != null) // T / CF
            ioMode = 1;
        else
            ioMode = 2;
        switch(ioMode){
            case -1:
                try{
                    throw new Exception("<ioMode> init failure") ;
                }catch (Exception e){
                    e.printStackTrace();
                }
                return;
            case 0:
                break;
            case 1:
                break;
            case 2:
                if(problemName.length() == 0){
                    try{
                        throw new Exception("<problemName> init failure");
                    }catch (Exception e){
                        e.printStackTrace();
                    }
                    return;
                }
            case 3:
                break;
        }
        io = new IO(ioMode, problemName);
        if(ioMode == 0){
            System.out.println("File output : \n<start>");
            System.out.flush();
            nanoTime = System.nanoTime();
        }
        solve();
        io.flush();
        if(ioMode == 0){
            System.out.println("</start>");
            long t = System.nanoTime() - nanoTime;
            int d3 = 1000000000, d2 = 1000000, d1 = 1000000;
            if(t>=d3)
                System.out.println(t/d3 + "." + t%d3 + " seconds");
            else if(t>=d2)
                System.out.println(t/d2 + "." + t%d2 + " millis");
            else if(t>=d1)
                System.out.println(t/d1 + "." + t%d1 + " millis");
            System.out.flush();
        }
    }

    private class TapeList {
        private class Node {
            Node left, right;
            char value;
            public Node(Node left, char value){
                this.left = left;
                this.value = value;
            }
            @Override
            public String toString(){
                return value + " ";
            }
        }
        private Node first, pnt;
        private int dir = 1;
        private TapeList(char seq[]){
            Node n0 = pnt = first = new Node(null, seq[0]), n1;
            for(int i = 1; i < seq.length; i++){
                n1 = new Node(n0, seq[i]);
                n0.right = n1;
                n0 = n1;
            }
        }
        public int[] doIt(int l, int r){
            pnt = first;
            int ind = l;
            for(int i = 1; i <= l; i++)
                pnt = pnt.right;
            int ans[] = new int[10];
            while(l <= ind && ind <= r){
                if('0' <= pnt.value && pnt.value <= '9'){
                    ans[pnt.value - '0']++;
                    if(pnt.value == '0'){
                        Node n1 = pnt.left, n2 = pnt.right;
                        if(dir == -1){
                            pnt = n1;
                            ind--;
                        }else{
                            pnt = n2;
                            //ind++;
                        }
                        n1.right = n2;
                        n2.left = n1;
                        r--;
                    }else{
                        pnt.value--;
                        if(dir == -1){
                            pnt = pnt.left;
                            ind--;
                        }else{
                            pnt = pnt.right;
                            ind++;
                        }
                    }
                }else{
                    if(pnt.value == '<'){
                        if(pnt.left.value == '<' || pnt.left.value == '>'){
                            r--;
                            Node n1 = pnt.left, n2 = pnt.right;
                            pnt = pnt.left;
                            n1.right = n2;
                            n2.left = n1;
                        }else{
                            pnt = pnt.left;
                            //ind++;
                        }
                        dir = -1;
                        ind--;
                    }else/* if(pnt.value == '>')*/{
                        if(pnt.right.value == '<' || pnt.right.value == '>'){
                            r--;
                            Node n1 = pnt.left, n2 = pnt.right;
                            pnt = pnt.right;
                            n1.right = n2;
                            n2.left = n1;
                        }else{
                            pnt = pnt.right;
                            ind++;
                        }
                        dir = 1;
                    }
                }
            }
            return ans;
        }
    }

    private void solve() throws IOException {
        int n = io.nI(), q = io.nI();
        char c[] = new char[n+2];
        io.nC();
        c[0] = '>'; c[n+1] = '<';
        for(int i = 1; i<=n; i++)
            c[i] = io.nC();io.setAlwaysFlush(true);
        //TapeList L = new TapeList(c);
        for(int i = 0; i<q; i++){
            int t[] = new TapeList(c).doIt(io.nI(), io.nI());
            for(int j = 0; j<t.length; j++)
                io.wf("%d ", t[j]);
            io.wln();
        }
    }//2.2250738585072012e-308

    /**
     * Input-output class
     * @author master_j
     * @version 0.2.4
     */
    @SuppressWarnings("unused")
    private class IO{
        private boolean alwaysFlush;
        StreamTokenizer in; PrintWriter out; BufferedReader br; Reader reader; Writer writer;
        public IO(int ioMode, String problemName) throws IOException{
            Locale.setDefault(Locale.US);
//         _______________________________________________ _________
//        |   Input Mode     |      Output Mode    | mode | comment |
//        |------------------|---------------------|----- |---------|
//        |   input.txt      |      System.out     |  0   |    mj   |
//        |   System.in      |      System.out     |  1   |  T / CF |
//        |<problemName>.in  |  <problemName>.out  |  2   |         |
//        |   input.txt      |      output.txt     |  3   |    C    |
//        |__________________|_____________________|______|_________|
            switch(ioMode){
                case 0:
                    reader = new FileReader("input.txt");
                    writer = new OutputStreamWriter(System.out);
                    break;
                case 1:
                    reader = new InputStreamReader(System.in);
                    writer = new OutputStreamWriter(System.out);
                    break;
                case 2:
                    reader = new FileReader(problemName + ".in");
                    writer = new FileWriter(problemName + ".out");
                    break;
                case 3:
                    reader = new FileReader("input.txt");
                    writer = new FileWriter("output.txt");
                    break;
            }
            br = new BufferedReader(reader);
            in = new StreamTokenizer(br);
            out = new PrintWriter(writer);
            alwaysFlush = false;
        }
        public void setAlwaysFlush(boolean arg){alwaysFlush = arg;}
        public void wln(){out.println(); if(alwaysFlush)flush();}
        public void wln(int arg){out.println(arg); if(alwaysFlush)flush();}
        public void wln(long arg){out.println(arg); if(alwaysFlush)flush();}
        public void wln(double arg){out.println(arg); if(alwaysFlush)flush();}
        public void wln(String arg){out.println(arg); if(alwaysFlush)flush();}
        public void wln(boolean arg){out.println(arg); if(alwaysFlush)flush();}
        public void wln(char arg){out.println(arg); if(alwaysFlush)flush();}
        public void wln(float arg){out.println(arg); if(alwaysFlush)flush();}
        public void wln(Object arg){out.println(arg); if(alwaysFlush)flush();}
        public void w(int arg){out.print(arg); if(alwaysFlush)flush();}
        public void w(long arg){out.print(arg); if(alwaysFlush)flush();}
        public void w(double arg){out.print(arg); if(alwaysFlush)flush();}
        public void w(String arg){out.print(arg); if(alwaysFlush)flush();}
        public void w(boolean arg){out.print(arg); if(alwaysFlush)flush();}
        public void w(char arg){out.print(arg); if(alwaysFlush)flush();}
        public void w(float arg){out.print(arg); if(alwaysFlush)flush();}
        public void w(Object arg){out.print(arg); if(alwaysFlush)flush();}
        public void wf(String format, Object...args){out.printf(format, args); if(alwaysFlush)flush();}
        public void flush(){out.flush();}
        public int nI() throws IOException {in.nextToken(); return(int)in.nval;}
        public long nL() throws IOException {in.nextToken(); return(long)in.nval;}
        public String nS() throws IOException {in.nextToken(); return in.sval;}
        public double nD() throws IOException {in.nextToken(); return in.nval;}
        public float nF() throws IOException {in.nextToken(); return (float)in.nval;}
        public char nC() throws IOException {return (char)br.read();}
        public void wc(char...arg){for(char c : arg){in.ordinaryChar(c);in.wordChars(c, c);}}
        public void wc(String arg){wc(arg.toCharArray());}
        public void wc(char arg0, char arg1){in.ordinaryChars(arg0, arg1); in.wordChars(arg0, arg1);}
        public boolean eof(){return in.ttype == StreamTokenizer.TT_EOF;}
        public boolean eol(){return in.ttype == StreamTokenizer.TT_EOL;}
    }
}