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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:36777216")
template <class T>
inline T &RD(T &);
template <class T>
inline void OT(const T &);
inline long long RD() {
  long long x;
  return RD(x);
}
inline char &RC(char &c) {
  scanf(" %c", &c);
  return c;
}
inline char RC() {
  char c;
  return RC(c);
}
inline long double &RF(long double &x) {
  scanf("%lf", &x);
  return x;
}
inline long double RF() {
  long double x;
  return RF(x);
}
inline char *RS(char *s) {
  scanf("%s", s);
  return s;
}
template <class T0, class T1>
inline T0 &RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
  return x0;
}
template <class T0, class T1, class T2>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
  return x0;
}
template <class T0, class T1, class T2, class T3>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
  return x0;
}
template <class T0, class T1>
inline void OT(const T0 &x0, const T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5, const T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
inline char &RC(char &a, char &b) {
  RC(a), RC(b);
  return a;
}
inline char &RC(char &a, char &b, char &c) {
  RC(a), RC(b), RC(c);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d) {
  RC(a), RC(b), RC(c), RC(d);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e) {
  RC(a), RC(b), RC(c), RC(d), RC(e);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
  return a;
}
inline long double &RF(long double &a, long double &b) {
  RF(a), RF(b);
  return a;
}
inline long double &RF(long double &a, long double &b, long double &c) {
  RF(a), RF(b), RF(c);
  return a;
}
inline long double &RF(long double &a, long double &b, long double &c,
                       long double &d) {
  RF(a), RF(b), RF(c), RF(d);
  return a;
}
inline long double &RF(long double &a, long double &b, long double &c,
                       long double &d, long double &e) {
  RF(a), RF(b), RF(c), RF(d), RF(e);
  return a;
}
inline long double &RF(long double &a, long double &b, long double &c,
                       long double &d, long double &e, long double &f) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
  return a;
}
inline long double &RF(long double &a, long double &b, long double &c,
                       long double &d, long double &e, long double &f,
                       long double &g) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
  return a;
}
inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2) {
  FLC(A0), FLC(A1), FLC(A2);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  FLC(A0), FLC(A1), FLC(A2), FLC(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5), FLC(A6);
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, less<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < int(n); ++i) CLR(A[i]);
}
template <class T>
inline T &SRT(T &A) {
  sort(A.begin(), A.end());
  return A;
}
template <class T, class C>
inline T &SRT(T &A, C B) {
  sort(A.begin(), A.end(), B);
  return A;
}
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long double EPS = 1e-8;
const long double OO = 1e15;
const long double PI = acos(-1.0);
template <class T>
inline void checkMin(T &a, const T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkMax(T &a, const T b) {
  if (b > a) a = b;
}
template <class T>
inline void checkMin(T &a, T &b, const T x) {
  checkMin(a, x), checkMin(b, x);
}
template <class T>
inline void checkMax(T &a, T &b, const T x) {
  checkMax(a, x), checkMax(b, x);
}
template <class T, class C>
inline void checkMin(T &a, const T b, C c) {
  if (c(b, a)) a = b;
}
template <class T, class C>
inline void checkMax(T &a, const T b, C c) {
  if (c(a, b)) a = b;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
inline int Ceil(int x, int y) { return (x - 1) / y + 1; }
inline bool _1(int x, int i) { return x & 1 << i; }
inline bool _1(long long x, int i) { return x & 1LL << i; }
inline long long _1(int i) { return 1LL << i; }
inline long long _U(int i) { return _1(i) - 1; };
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
template <class T>
inline T high_bit(T x) {
  T p = low_bit(x);
  while (p != x) x -= p, p = low_bit(x);
  return p;
}
template <class T>
inline T cover_bit(T x) {
  T p = 1;
  while (p < x) p <<= 1;
  return p;
}
inline int count_bits(int x) {
  x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
  x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
  x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
  x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
  x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
  return x;
}
inline int count_bits(long long x) {
  x = (x & 0x5555555555555555LL) + ((x & 0xaaaaaaaaaaaaaaaaLL) >> 1);
  x = (x & 0x3333333333333333LL) + ((x & 0xccccccccccccccccLL) >> 2);
  x = (x & 0x0f0f0f0f0f0f0f0fLL) + ((x & 0xf0f0f0f0f0f0f0f0LL) >> 4);
  x = (x & 0x00ff00ff00ff00ffLL) + ((x & 0xff00ff00ff00ff00LL) >> 8);
  x = (x & 0x0000ffff0000ffffLL) + ((x & 0xffff0000ffff0000LL) >> 16);
  x = (x & 0x00000000ffffffffLL) + ((x & 0xffffffff00000000LL) >> 32);
  return x;
}
inline int reverse_bits(int x) {
  x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
  x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
  x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
  x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
  x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
  return x;
}
inline long long reverse_bits(long long x) {
  x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
  x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
  x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
  x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
  x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
  return x;
}
inline void INC(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int sum(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void DEC(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
}
inline int dff(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}
inline void MUL(int &a, int b) { a = (long long)a * b % MOD; }
inline int pdt(int a, int b) { return (long long)a * b % MOD; }
inline int sum(int a, int b, int c) { return sum(sum(a, b), c); }
inline int sum(int a, int b, int c, int d) { return sum(sum(a, b), sum(c, d)); }
inline int pdt(int a, int b, int c) { return pdt(pdt(a, b), c); }
inline int pdt(int a, int b, int c, int d) { return pdt(pdt(pdt(a, b), c), d); }
inline int pow(int a, long long b) {
  int c(1);
  while (b) {
    if (b & 1) MUL(c, a);
    MUL(a, a), b >>= 1;
  }
  return c;
}
template <class T>
inline T pow(T a, long long b) {
  T c(1);
  while (b) {
    if (b & 1) c *= a;
    a *= a, b >>= 1;
  }
  return c;
}
inline int _I(int b) {
  int a = MOD, x1 = 0, x2 = 1, q;
  while (true) {
    q = a / b, a %= b;
    if (!a) return (x2 + MOD) % MOD;
    DEC(x1, pdt(q, x2));
    q = b / a, b %= a;
    if (!b) return (x1 + MOD) % MOD;
    DEC(x2, pdt(q, x1));
  }
}
inline void DIA(int &a, int b) { MUL(a, _I(b)); }
inline int qtt(int a, int b) { return pdt(a, _I(b)); }
inline int phi(int n) {
  int res = n;
  for (int i = 2; sqr(i) <= n; ++i)
    if (!(n % i)) {
      DEC(res, qtt(res, i));
      do {
        n /= i;
      } while (!(n % i));
    }
  if (n != 1) DEC(res, qtt(res, n));
  return res;
}
struct Po;
struct Line;
struct Seg;
inline int sgn(long double x) { return x < -EPS ? -1 : x > EPS; }
inline int sgn(long double x, long double y) { return sgn(x - y); }
struct Po {
  long double x, y;
  Po(long double _x = 0, long double _y = 0) : x(_x), y(_y) {}
  friend istream &operator>>(istream &in, Po &p) { return in >> p.x >> p.y; }
  friend ostream &operator<<(ostream &out, Po p) {
    return out << "(" << p.x << ", " << p.y << ")";
  }
  friend bool operator==(Po, Po);
  friend bool operator!=(Po, Po);
  friend Po operator+(Po, Po);
  friend Po operator-(Po, Po);
  friend Po operator*(Po, long double);
  friend Po operator/(Po, long double);
  bool operator<(const Po &rhs) const {
    return sgn(x, rhs.x) < 0 || sgn(x, rhs.x) == 0 && sgn(y, rhs.y) < 0;
  }
  Po operator-() const { return Po(-x, -y); }
  Po &operator+=(Po rhs) {
    x += rhs.x, y += rhs.y;
    return *this;
  }
  Po &operator-=(Po rhs) {
    x -= rhs.x, y -= rhs.y;
    return *this;
  }
  Po &operator*=(long double k) {
    x *= k, y *= k;
    return *this;
  }
  Po &operator/=(long double k) {
    x /= k, y /= k;
    return *this;
  }
  long double length_sqr() const { return sqr(x) + sqr(y); }
  long double length() const { return sqrt(length_sqr()); }
  Po unit() const { return (*this) / length(); }
  bool dgt() const { return !sgn(x) && !sgn(y); }
  long double atan() const { return atan2(y, x); }
  void input() { scanf("%lf %lf", &x, &y); }
};
bool operator==(Po a, Po b) {
  return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
}
bool operator!=(Po a, Po b) {
  return sgn(a.x - b.x) != 0 || sgn(a.y - b.y) != 0;
}
Po operator+(Po a, Po b) { return Po(a.x + b.x, a.y + b.y); }
Po operator-(Po a, Po b) { return Po(a.x - b.x, a.y - b.y); }
Po operator*(Po a, long double k) { return Po(a.x * k, a.y * k); }
Po operator*(long double k, Po a) { return a * k; }
Po operator/(Po a, long double k) { return Po(a.x / k, a.y / k); }
struct Line {
  Po a, b;
  Line(const Po &a = Po(), const Po &b = Po()) : a(a), b(b) {}
  Line(const Line &l) : a(l.a), b(l.b) {}
  Line(long double x0, long double y0, long double x1, long double y1)
      : a(Po(x0, y0)), b(Po(x1, y1)) {}
  void getequation(long double, long double, long double) const;
  Line operator+(Po x) const { return Line(a + x, b + x); }
  friend ostream &operator<<(ostream &out, Line p) {
    return out << p.a << "-" << p.b;
  }
  long double length() const { return (b - a).length(); }
  bool dgt() const { return (a - b).dgt(); }
  void input() { a.input(), b.input(); }
};
struct Seg : Line {
  Seg(const Po &a = Po(), const Po &b = Po()) : Line(a, b) {}
  Seg(const Line &l) : Line(l) {}
  Seg(long double x0, long double y0, long double x1, long double y1)
      : Line(x0, y0, x1, y1) {}
};
inline long double dot(const long double &x1, const long double &y1,
                       const long double &x2, const long double &y2) {
  return x1 * x2 + y1 * y2;
}
inline long double dot(const Po &a, const Po &b) {
  return dot(a.x, a.y, b.x, b.y);
}
inline long double dot(const Po &p0, const Po &p1, const Po &p2) {
  return dot(p1 - p0, p2 - p0);
}
inline long double dot(const Po &o, const Line &l) { return dot(o, l.a, l.b); }
inline long double dot(const Line &l, const Po &o) { return dot(o, l.a, l.b); }
inline long double dot(const Line &l1, const Line &l2) {
  return dot(l1.b - l1.a, l2.b - l2.a);
}
inline long double det(const long double &x1, const long double &y1,
                       const long double &x2, const long double &y2) {
  return x1 * y2 - x2 * y1;
}
inline long double det(const Po &a, const Po &b) {
  return det(a.x, a.y, b.x, b.y);
}
inline long double det(const Po &p0, const Po &p1, const Po &p2) {
  return det(p1 - p0, p2 - p0);
}
inline long double det(const Po &o, const Line &l) { return det(o, l.a, l.b); }
inline long double det(const Line &l, const Po &o) { return det(o, l.a, l.b); }
inline long double det(const Line &l1, const Line &l2) {
  return det(l1.b - l1.a, l2.b - l2.a);
}
void Line::getequation(long double A, long double B, long double C) const {
  A = a.y - b.y, B = b.x - a.x, C = det(a, b);
}
template <class T1, class T2>
inline long double dist(const T1 &x, const T2 &y) {
  return sqrt(dist_sqr(x, y));
}
template <class T1, class T2, class T3>
inline long double dist(const T1 &x, const T2 &y, const T3 &z) {
  return sqrt(dist_sqr(x, y, z));
}
template <class T1, class T2>
inline int dett(const T1 &x, const T2 &y) {
  return sgn(det(x, y));
}
template <class T1, class T2>
inline int dott(const T1 &x, const T2 &y) {
  return sgn(dot(x, y));
}
template <class T1, class T2, class T3>
inline int dett(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(det(x, y, z));
}
template <class T1, class T2, class T3>
inline int dott(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(dot(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(det(x, y, z, w));
}
template <class T1, class T2, class T3, class T4>
inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(dot(x, y, z, w));
}
inline long double dist_sqr(const long double &x, const long double &y) {
  return sqr(x) + sqr(y);
}
inline long double dist_sqr(const long double &x, const long double &y,
                            const long double &z) {
  return sqr(x) + sqr(y) + sqr(z);
}
inline long double dist_sqr(const Po &a, const Po &b) {
  return sqr(a.x - b.x) + sqr(a.y - b.y);
}
inline long double dist_sqr(const Po &p, const Line &l) {
  Po v0 = l.b - l.a, v1 = p - l.a;
  return sqr(fabs(det(v0, v1))) / v0.length_sqr();
}
inline long double dist_sqr(const Po &p, const Seg &l) {
  Po v0 = l.b - l.a, v1 = p - l.a, v2 = p - l.b;
  if (sgn(dot(v0, v1)) * sgn(dot(v0, v2)) <= 0)
    return dist_sqr(p, Line(l));
  else
    return min(v1.length_sqr(), v2.length_sqr());
}
inline long double dist_sqr(Line l, Po p) { return dist_sqr(p, l); }
inline long double dist_sqr(Seg l, Po p) { return dist_sqr(p, l); }
inline long double dist_sqr(Line l1, Line l2) {
  if (sgn(det(l1, l2)) != 0) return 0;
  return dist_sqr(l1.a, l2);
}
inline long double dist_sqr(Line l1, Seg l2) {
  Po v0 = l1.b - l1.a, v1 = l2.a - l1.a, v2 = l2.b - l1.a;
  long double c1 = det(v0, v1), c2 = det(v0, v2);
  return sgn(c1) != sgn(c2) ? 0
                            : sqr(min(fabs(c1), fabs(c2))) / v0.length_sqr();
}
bool isIntersect(Seg l1, Seg l2) {
  if (l1.a == l2.a || l1.a == l2.b || l1.b == l2.a || l1.b == l2.b) return true;
  return min(l1.a.x, l1.b.x) <= max(l2.a.x, l2.b.x) &&
         min(l2.a.x, l2.b.x) <= max(l1.a.x, l1.b.x) &&
         min(l1.a.y, l1.b.y) <= max(l2.a.y, l2.b.y) &&
         min(l2.a.y, l2.b.y) <= max(l1.a.y, l1.b.y) &&
         sgn(det(l1.a, l2.a, l2.b)) * sgn(det(l1.b, l2.a, l2.b)) <= 0 &&
         sgn(det(l2.a, l1.a, l1.b)) * sgn(det(l2.b, l1.a, l1.b)) <= 0;
}
inline long double dist_sqr(Seg l1, Seg l2) {
  if (isIntersect(l1, l2))
    return 0;
  else
    return min(dist_sqr(l1.a, l2), dist_sqr(l1.b, l2), dist_sqr(l2.a, l1),
               dist_sqr(l2.b, l1));
}
inline bool isOnSide(const Po &p, const Seg &l) { return p == l.a || p == l.b; }
inline bool isOnSeg(const Po &p, const Seg &l) {
  return sgn(det(p, l.a, l.b)) == 0 && sgn(l.a.x, p.x) * sgn(l.b.x, p.x) <= 0 &&
         sgn(l.a.y, p.y) * sgn(l.b.y, p.y) <= 0;
}
inline bool isOnSegg(const Po &p, const Seg &l) {
  return sgn(det(p, l.a, l.b)) == 0 && sgn(l.a.x, p.x) * sgn(l.b.x, p.x) < 0 &&
         sgn(l.a.y, p.y) * sgn(l.b.y, p.y) < 0;
}
inline Po intersect(const Line &l1, const Line &l2) {
  return l1.a + (l1.b - l1.a) * (det(l2.a, l1.a, l2.b) / det(l2, l1));
}
inline Po intersect(const Po &p, const Line &l) {
  return intersect(Line(p, p + Po(l.a.y - l.b.y, l.b.x - l.a.x)), l);
}
inline Po rotate(Po p, long double alpha, Po o = Po()) {
  p.x -= o.x, p.y -= o.y;
  return Po(p.x * cos(alpha) - p.y * sin(alpha),
            p.y * cos(alpha) + p.x * sin(alpha)) +
         o;
}
inline int rand32() {
  return (bool(rand() & 1) << 30) | (rand() << 15) + rand();
}
inline int random32(int l, int r) { return rand32() % (r - l + 1) + l; }
inline int random(int l, int r) { return rand() % (r - l + 1) + l; }
int dice() { return rand() % 6; }
bool coin() { return rand() % 2; }
namespace Clock {
long double st, rd, ed;
inline long double getTime() { return 1.0 * clock() / CLOCKS_PER_SEC; }
inline void start() { st = getTime(); }
inline long double elapsed() { return getTime() - st; }
}  // namespace Clock
template <class T>
inline T &RD(T &x) {
  char c;
  for (c = getchar(); c < '0'; c = getchar())
    ;
  x = c - '0';
  for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
  return x;
}
int ____Case;
template <class T>
inline void OT(const T &x) {
  printf("%d ", x);
}
const int N = 100009, M = 2 * N;
char str[N];
int num[N];
int l[N], r[N];
int n, m;
struct Query;
vector<Query *> P[N];
vector<Query *> O[N];
struct Query {
  int c[10], x, y;
  bool act;
  void input() {
    RD(x, y);
    --x, --y;
    P[x].push_back(this);
  }
  void output() {
    for (int i = 0; i < int(10); ++i) OT(c[i]);
    puts("");
  }
  void st(int t[]) {
    act = true;
    O[l[x]].push_back(this), O[r[y]].push_back(this);
    for (int i = 0; i < int(10); ++i) c[i] -= t[i];
  }
  int id();
  void ed(int t[]) {
    if (act) {
      act = false;
      for (int i = 0; i < int(10); ++i) c[i] += t[i];
    }
  }
} Q[N];
int Query::id() { return this - Q; }
void del(int p) {
  r[l[p]] = r[p];
  l[r[p]] = l[p];
}
struct Interpreter {
  int cp, dp, rr;
  int c[10];
  void run(int _cp) {
    vector<Query *> cur;
    RST(c);
    cp = _cp;
    dp = 1;
    rr = 0;
    while (true) {
      if (cp < _cp || cp >= n) break;
      checkMax(rr, cp);
      for (int i = 0; i < int(int(O[cp].size())); ++i) O[cp][i]->ed(c);
      CLR(O[cp]);
      if (!P[cp].empty()) {
        for (int i = 0; i < int(int(P[cp].size())); ++i) {
          cur.push_back(P[cp][i]);
          P[cp][i]->st(c);
        }
        CLR(P[cp]);
      }
      if (isdigit(str[cp])) {
        ++c[num[cp]--];
        if (num[cp] == -1) del(cp);
        cp = dp == 1 ? r[cp] : l[cp];
      } else {
        dp = str[cp] == '>';
        int _cp = cp;
        cp = dp == 1 ? r[cp] : l[cp];
        if (!isdigit(str[cp])) del(_cp);
      }
    }
    for (int i = 0; i < int(int(O[cp].size())); ++i) O[cp][i]->ed(c);
    CLR(O[cp]);
    if (rr != n - 1) run(rr + 1);
  }
} I;
int main() {
  RD(n, m);
  RS(str);
  for (int i = 0; i < int(n); ++i)
    num[i] = str[i] - 48, l[i] = i - 1, r[i] = i + 1;
  for (int i = 0; i < int(m); ++i) Q[i].input();
  I.run(0);
  for (int i = 0; i < int(m); ++i) Q[i].output();
}