Lexicographical Substring Sort

You are given a permutation \(a\) of \(\{1,2,\ldots,n\}\) (each integer from 1 to \(n\) appears exactly once). A substring of \(a\) is defined as any contiguous segment \(a_l, a_{l+1}, \ldots, a_r\) where \(1 \le l \le r \le n\). We denote this substring as \(a_{l\sim r}\), and call \(l\) its left endpoint and \(r\) its right endpoint.

You are required to sort all substrings of \(a\) in lexicographical order. The lexicographical order for two sequences \(p\) and \(q\) is defined as follows: \(p<q\) if and only if there exists a natural number \(k\) such that the first \(k\) numbers of \(p\) and \(q\) are equal, and \(p_{k+1} < q_{k+1}\). In particular, if \(p\) is a prefix of \(q\) and \(p \neq q\), then we also consider \(p<q\).

For example:

• \([1,2] < [3,2]\) (compare at \(k=0\))
• \([3,1,100] < [3,2,1]\) (compare at \(k=1\))
• \([3,4] < [3,4,6]\) (since the first sequence is a prefix of the second)

You will then be given \(q\) queries. For each query, an integer \(k\) is presented. You must determine the left and right endpoints \((l, r)\) of the substring which is the \(k\)-th smallest in the lexicographical order.

inputFormat

The first line of input contains two integers \(n\) and \(q\) \((1 \leq n, q \leq 10^3)\) — the size of the permutation and the number of queries, respectively.

The second line contains \(n\) distinct integers \(a_1, a_2, \ldots, a_n\), which represent a permutation of \(\{1,2,\ldots,n\}\).

Each of the following \(q\) lines contains one integer \(k\) representing a query. It is guaranteed that \(k\) is valid (i.e. \(1 \le k \le \frac{n(n+1)}{2}\)).

outputFormat

For each query, output two integers \(l\) and \(r\) separated by a space, representing the left and right endpoints of the \(k\)-th smallest substring in lexicographical order.

sample

3 2
1 2 3
1
6

1 1
3 3