A12766 | 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.