题目描述

给定一个包含 $n$ 个数的序列，第 $k$ 个数为 $a[k]$。

你需要回答 $m$ 个询问。

每个询问的要求是：对于 $k$ 从 $1$ 到 $10$ 的每一个值，计算区间 $[l,r]$ 中满足条件的对 $(x, x+k-1)$ 的数量。

我们称一对 $(x,y)$ 是 有效的，当且仅当：

1. 对于从 $x$ 到 $y$ 的每一个 $i$，区间 $[l,r]$ 中至少存在一个元素等于 $i$；
2. 区间 $[l,r]$ 中不存在等于 $x-1$ 或 $y+1$ 的元素。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $T$ $(1 \le T \le 5)$，表示测试数据的组数。

对于每组测试数据：

第一行包含两个整数 $n, m$ $(1 \le n,m \le 1000000)$。

接下来一行包含 $n$ 个整数，依次表示 $a[1],\dots, a[n]$ $(0 \le a[i] \le 2000000000)$。

随后的 $m$ 行，每行包含两个整数 $l, r$，表示一个针对区间 $[l,r]$ 的询问 $(1 \le l \le r \le n)$。

输出格式

对于每个询问，你需要输出 $10$ 个数。为减少输出量，只需将每个数对 $10$ 取模后输出，中间不加空格。

对于每组测试数据，输出 $m$ 行。第 $k$ 行包含一个长度为 $10$ 的字符串，表示第 $k$ 个询问的答案。

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

0110000000
0100000000
0100000000
0010000000
0100000000

提示

翻译由 DeepSeek V4 Pro 完成