Problem Statement

You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$.

For a pair of integers $(l, r) \ (1\leq l\lt r\leq N)$, let $f(l,r)$ be the integer sequence obtained by swapping the $l$-th element and the $r$-th element of $A$.

Generate a sequence of integer sequences $B=(B_1,B_2,\ldots,B_{\frac{N(N-1)}{2}})$ of length $\frac{N(N-1)}{2}$ by the following procedure:

• Prepare an empty sequence $B=()$.
• For each pair of integers $(l, r)\ (1\leq l\lt r\leq N)$, add $f(l,r)$ to $B$.
• Sort $B$ in lexicographical order of sequences.

You are given $Q$ queries; process them in order. The $i$-th query is as follows:

• Given an integer $k$, find one pair of integers $(l, r) \ (1\leq l\lt r\leq N)$ such that $B_k=f(l,r)$ and output it.

What is lexicographical order of sequences? A sequence $S = (S_1,S_2,\ldots,S_{|S|})$ is lexicographically smaller than a sequence $T = (T_1,T_2,\ldots,T_{|T|})$ if and only if one of the following two conditions holds. Here, $|S|$ and $|T|$ represent the lengths of $S$ and $T$, respectively. $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$. There exists an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following hold: $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$ $S_i$ is smaller than $T_i$ (as a number).

Constraints

• $2\leq N\leq 2\times 10^5$
• $1\leq Q\leq 2\times 10^5$
• $1\leq A_i\leq N$
• $1\leq k\leq \frac{N(N-1)}{2}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

k

Output

Output $Q$ lines. The $i$-th line should contain the answer to the $i$-th query in the following format:

l r

If there are multiple solutions, any of them will be considered correct.