Chtholly has given you a sequence. For each query, you need to find the number of maximal value-range contiguous segments of lengths $1, 2, \ldots, 10$ within a given interval. A value-range contiguous segment is defined as follows:

• Sort all the numbers in the interval and remove duplicates to obtain a sequence $b$.
• If a pair $(l, r)$ satisfies that each number in $b_l, b_{l+1}, \ldots, b_r$ is equal to the previous number plus $1$.
• Furthermore, if the pairs $(l, r+1)$ and $(l-1, r)$ do not satisfy this condition, we call $(l, r)$ a maximal value-range contiguous segment of length $r-l+1$.

Input

The first line contains two integers $n$ and $m$, representing the length of the sequence and the number of queries, respectively.

The next line contains $n$ integers representing the sequence.

The following $m$ lines each contain two integers $l$ and $r$, representing the query interval.

Output

For each query, output a string of length $10$, where the $i$-th character represents the number of maximal contiguous segments of length $i$ modulo $10$.

Examples

Input 1

8 9
2 3 3 3 3 6 6 6
1 8
2 3
4 5
6 8
1 2
3 4
5 6
3 8
5 5

Output 1

1100000000
1000000000
1000000000
1000000000
0100000000
1000000000
2000000000
2000000000
1000000000

Note

Idea: nzhtl1477, Solution: nzhtl1477, Code: mcfx, Data: nzhtl1477

For $100\%$ of the data, $1\leq n, m, a_i \leq 10^6$, $1\leq l \leq r \leq n$.