Lập trình băng giấy

Xét một ngôn ngữ lập trình đơn giản, trong đó mỗi chương trình là một dãy không rỗng gồm các ký tự "<", ">" và các chữ số.

Bộ thông dịch của ngôn ngữ hoạt động dựa trên một con trỏ lệnh gồm hai phần:

• Con trỏ ký tự hiện tại (CP) — chỉ tới một ký tự trong dãy.
• Con trỏ hướng (DP) — có thể trỏ sang trái hoặc phải.

Ban đầu CP trỏ tới ký tự ngoài cùng bên trái của dãy, còn DP trỏ sang phải.

Ta lặp lại các bước sau cho đến thời điểm đầu tiên mà CP trỏ ra ngoài dãy:

• Nếu CP đang trỏ vào một chữ số, bộ thông dịch in chữ số đó ra, sau đó CP dịch một bước theo hướng của DP. Sau khi dịch, giá trị của chữ số vừa in trong dãy giảm đi $1$. Nếu chữ số vừa in là $0$ thì nó không thể giảm thêm, nên ký tự đó bị xóa khỏi dãy và độ dài dãy giảm đi $1$.
• Nếu CP đang trỏ vào "<" hoặc ">", DP đổi hướng tương ứng thành trái hoặc phải. Sau đó CP dịch một bước theo DP. Nếu ký tự mới mà CP trỏ tới cũng là "<" hoặc ">" thì ký tự trước đó (ký tự vừa rời khỏi) bị xóa khỏi dãy.

Khi CP đi ra ngoài dãy, chương trình kết thúc. Có thể chứng minh mọi chương trình trong ngôn ngữ này đều kết thúc sau hữu hạn bước.

Cho dãy $s_1,s_2,\dots ,s_n$ gồm các ký tự "<", ">" và chữ số. Bạn cần trả lời $q$ truy vấn. Mỗi truy vấn cho hai số $l$ và $r$ và hỏi: nếu chạy dãy con $s_l,s_{l+1},\dots ,s_r$ như một chương trình độc lập theo ngôn ngữ trên thì mỗi chữ số được in ra bao nhiêu lần.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$ — độ dài dãy $s$ và số truy vấn.
• Dòng thứ hai chứa dãy $s$ gồm các ký tự "<", ">" và chữ số (0..9), viết liền nhau không có dấu cách.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$ — truy vấn thứ $i$.

Dữ liệu ra

Với mỗi truy vấn, in ra $10$ số nguyên cách nhau bởi dấu cách: $x_0,x_1,\dots ,x_9$, trong đó $x_i$ là số lần bộ thông dịch in ra chữ số $i$ khi chạy chương trình tương ứng. In đáp án theo đúng thứ tự các truy vấn.

Ràng buộc

• $1\le n,q\le 100$
• $1\le l_i\le r_i\le n$

Ví dụ