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

当你任意选一对 $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<q$），当且仅当存在自然数 $k$ 使 $p,q$ 的前 $k$ 个数相同且 $p_{k+1}<q_{k+1}$。

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

例如：
- $[1,2]<[3,2]$（当 $k=0$）
- $[3,1,100]<[3,2,1]$（当 $k=1$）
- $[3,4]<[3,4,6]$（$p$ 是 $q$ 前缀）

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

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

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

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

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

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

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