CF1179A.Valeriy and Deque

Recently, on the course of algorithms and data structures, Valeriy learned how to use a deque. He built a deque filled with $n$ elements. The $i$ -th element is $a_i$ ( $i$ = $1, 2, \ldots, n$ ). He gradually takes the first two leftmost elements from the deque (let's call them $A$ and $B$ , respectively), and then does the following: if $A > B$ , he writes $A$ to the beginning and writes $B$ to the end of the deque, otherwise, he writes to the beginning $B$ , and $A$ writes to the end of the deque. We call this sequence of actions an operation.

For example, if deque was $[2, 3, 4, 5, 1]$ , on the operation he will write $B=3$ to the beginning and $A=2$ to the end, so he will get $[3, 4, 5, 1, 2]$ .

The teacher of the course, seeing Valeriy, who was passionate about his work, approached him and gave him $q$ queries. Each query consists of the singular number $m_j$ $(j = 1, 2, \ldots, q)$ . It is required for each query to answer which two elements he will pull out on the $m_j$ -th operation.

Note that the queries are independent and for each query the numbers $A$ and $B$ should be printed in the order in which they will be pulled out of the deque.

Deque is a data structure representing a list of elements where insertion of new elements or deletion of existing elements can be made from both sides.

The first line contains two integers $n$ and $q$ ( $2 \leq n \leq 10^5$ , $0 \leq q \leq 3 \cdot 10^5$ ) — the number of elements in the deque and the number of queries. The second line contains $n$ integers $a_1$ , $a_2$ , ..., $a_n$ , where $a_i$ $(0 \leq a_i \leq 10^9)$ — the deque element in $i$ -th position. The next $q$ lines contain one number each, meaning $m_j$ ( $1 \leq m_j \leq 10^{18}$ ).

For each teacher's query, output two numbers $A$ and $B$ — the numbers that Valeriy pulls out of the deque for the $m_j$ -th operation.

Consider all 10 steps for the first test in detail:2. $[1, 2, 3, 4, 5]$ — on the first operation, $A$ and $B$ are $1$ and $2$ , respectively.So, $2$ we write to the beginning of the deque, and $1$ — to the end.

We get the following status of the deque: $[2, 3, 4, 5, 1]$ .
3. $[2, 3, 4, 5, 1] \Rightarrow A = 2, B = 3$ .
4. $[3, 4, 5, 1, 2]$
5. $[4, 5, 1, 2, 3]$
6. $[5, 1, 2, 3, 4]$
7. $[5, 2, 3, 4, 1]$
8. $[5, 3, 4, 1, 2]$
9. $[5, 4, 1, 2, 3]$
10. $[5, 1, 2, 3, 4]$
11. $[5, 2, 3, 4, 1] \Rightarrow A = 5, B = 2$ .