题目描述

给定一个长度为 n的数列 $a_{1}$,$a_{2}$,…,$a_n$。小珅会对你进行 q次询问，每次询问要求你计算出在区间 [l,l+1,…,r] 即[al,al+1,…,ar] 中出现次数最多的十进制数码是谁（0∼9 中的一个）以及该十进制数码出现了多少次，如果有多个数码出现次数相同，则选择数值最小的数码。

例如，对于数列$a={12,567,8791,22341,5674,778,123}$，区间 [2,5] 即 [$a_{2}$,$a_{3}$,…,$a_{5}$]中：

· 0出现了 0 次，没有任何整数包含数码 0；

· 1 出现了 2 次，8791 和22341 分别包含一个数码 1；

· 2 出现了 2 次，22341 包含两个数码 1；

· 3 出现了 1 次，22341 包含一个数码 3；

· 4 出现了 2 次22341 和 5674 分别包含一个数码 4；

· 5 出现了 2 次，567 和 56745674 分别包含一个数码 5；

· 6 出现了 2 次，567 和 5674 分别包含一个数码66；

· 7 出现了 3 次，567、8791 和 5674 分别包含一个数码 7；

· 8 出现了 1 次，18791 包含一个数码 8；

· 9 出现了 1 次，8791 包含一个数码 9。

因此，区间 [2,5]中最多数码为 7，出现了 3 次。

输入格式

第一行，包含两个正整数 n,q；

第二行，包含 n 个整数 $a_{1}$,$a_{2}$,…,$a_n$

接下来 q 行，每行两个整数 $l_i$,$r_i$，表示第 i 次询问的区间。

输出格式

共 q 行，每行两个整数，表示第i 次询问的区间中出现次数最多的数码和其出现次数。

样例输入

10 3
366 417 108 275 487 54 587 897 185 630
6 7
2 5
1 1

样例输出

5 2
7 3
6 2

提示

$1\le l_i\le r_i\le n\le 2\times 10^{5},1\le q\le 2\times 10^{5},0\le a_i\le 10^{9}$

1 1
0
1 1

0 1

7 5
81 13 93 29 73 57 1 
2 3
2 2
2 4
5 7
2 4

3 2
1 1
3 2
7 2
3 2

10 3
366 417 108 275 487 54 587 897 185 630
6 7
2 5
1 1

5 2
7 3
6 2