Problem Description

You are given a sequence of $n$ numbers, the $k$-th number is $a[k]$.

You need to answer $m$ queries.

Each query is: for each $k$ from $1$ to $10$, calculate the number of valid pairs $(x, x+k-1)$ in range $[l,r]$.

We call a pair $(x,y)$ valid when:

1. For each $i$ from $x$ to $y$, there exists at least one element in range $[l,r]$ which is equal to $i$.
2. There is no element in range $[l,r]$ which is equal to $x-1$ or $y+1$.

Input Format

The input contains multiple test cases.

The first line contains a number $T$ $(1 \le T \le 5)$ denoting the number of test cases.

In each test case:

The first line contains two numbers $n, m$. $(1 \le n,m \le 1000000)$.

Then one line contains $n$ numbers indicating $a[1]\dots a[n]$. $(0 \le a[i] \le 2000000000)$

The following $m$ lines each contain two numbers $l, r$ denoting a query in range $[l,r]$. $(1 \le l \le r \le n)$

Output Format

For each query you need to output $10$ numbers. In order to reduce the amount of output, you just need to output each number mod $10$, without space.

For each test case, output $m$ lines. The $k$-th line contains a string of length $10$ indicating the answers of the $k$-th query.

1
5 5
1 2 4 5 6
1 5
1 2
3 4
3 5
4 5

0110000000
0100000000
0100000000
0010000000
0100000000