题目描述

你有一个数列 $a$，其中 $1\sim n$ 各出现了一次（即 $a$ 是一个排列）。

当你任意选一对 $1\le l\le r\le n$，并将 $a_l,a_{l+1},\ldots,a_r$ 排成一行，你就得到了 $a$ 的一个子串，记为 $a_{l\sim r}$，称 $l$ 为左端点，$r$ 为右端点。

你需要把 $a$ 的所有子串按字典序从小到大排序。为了避免输出量过大，题目给出 $q$ 个询问，每次给出一个 $k$，求字典序第 $k$ 小的子串的左右端点。

如果你不知道什么是字典序，看这里：

对于两个数列 $p,q$，称 $p$ 的字典序小于 $q$（记为 $p\lt q$），当且仅当存在自然数 $k$ 使 $p,q$ 的前 $k$ 个数相同且 $p_{k+1}\lt q_{k+1}$。

特别地，若 $p$ 是 $q$ 的前缀且 $p\ne q$，也认为 $p$ 的字典序小于 $q$。

例如：

• $[1,2]\lt [3,2]$（当 $k=0$）
• $[3,1,100]\lt [3,2,1]$（当 $k=1$）
• $[3,4]\lt [3,4,6]$（$p$ 是 $q$ 前缀）

输入格式

输入的第一行有两个正整数 $n,q$ 表示序列长度和询问个数。

第二行有 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示这个数列。

之后有 $q$ 行，每行有一个正整数 $k$，表示要求的子串的排名。

输出格式

对于每个问题，输出一行两个整数 $l,r$，表示字典序第 $k$ 小的子串是 $a_{l\sim r}$。

样例

3 6
3 1 2
1
2
3
4
5
6

2 2
2 3
3 3
1 1
1 2
1 3

50 25
42 22 27 8 44 11 14 31 37 10 48 15 12 40 13 4 25 9 19 5 2 18 6 1 32 3 38 33 43 34 46 47 23 35 21 20 45 39 50 7 36 17 24 29 16 30 49 26 28 41
1178
991
755
1094
689
132
671
635
421
659
448
334
327
213
1206
453
1160
583
388
781
150
692
23
1162
62

37 48
27 44
3 28
1 46
43 47
20 34
33 37
2 19
15 44
2 43
7 27
6 31
6 24
4 29
32 37
7 32
5 44
19 47
13 47
44 45
23 24
43 50
24 46
5 46
26 30

提示

【样例解释 #1】

数列 $3,1,2$ 共有 $6$ 个子串，从小到大排序的结果为：$[1],[1,2],[2],[3],[3,1],[3,1,2]$。

【数据范围】

对于全体数据，保证 $1\le n,q\le 3\times 10^5$，$1\le k\le \dfrac{n(n+1)}{2}$，$a_i$ 中 $1\sim n$ 各有一个，输入皆为整数。