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 \gt 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.

最近，在算法与数据结构课程中，瓦列里学会了如何使用双端队列（deque）。他构建了一个包含 $n$ 个元素的双端队列。第 $i$ 个元素为 $a_i$（其中 $i = 1, 2, \ldots, n$）。他逐步从双端队列最左侧取出前两个元素（分别记为 $A$ 和 $B$），然后执行如下操作：若 $A > B$，则将 $A$ 插入双端队列头部，并将 $B$ 插入双端队列尾部；否则，将 $B$ 插入双端队列头部，并将 $A$ 插入双端队列尾部。我们将这一系列动作称为一次操作。

例如，若双端队列为 $[2, 3, 4, 5, 1]$，在一次操作中，他将 $B = 3$ 插入头部，$A = 2$ 插入尾部，从而得到新双端队列 $[3, 4, 5, 1, 2]$。

课程教师见瓦列里热情投入，便走近他，并向他提出了 $q$ 个查询。每个查询仅包含一个整数 $m_j$（其中 $j = 1, 2, \ldots, q$）。对每个查询，需回答：在第 $m_j$ 次操作中，他将从双端队列中取出哪两个元素。

注意：各查询相互独立；对每个查询，应按实际从双端队列中取出的顺序输出 $A$ 和 $B$。

双端队列（deque）是一种数据结构，表示一个元素列表，允许在列表两端进行新元素的插入或已有元素的删除。

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}$).

第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 10^5$，$0 \leq q \leq 3 \cdot 10^5$）—— 分别表示双端队列中的元素个数和查询次数。
第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$，其中 $a_i$（$0 \leq a_i \leq 10^9$）表示双端队列中第 $i$ 个位置的元素。
接下来的 $q$ 行每行包含一个整数，表示 $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.

对于每位教师的查询，输出两个数 $A$ 和 $B$ —— 即 Valeriy 在第 $m_j$ 次操作中从双端队列中取出的两个数。

Consider all 10 steps for the first test in detail:1. $[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]$.

2. $[2, 3, 4, 5, 1] \Rightarrow A = 2, B = 3$.
3. $[3, 4, 5, 1, 2]$
4. $[4, 5, 1, 2, 3]$
5. $[5, 1, 2, 3, 4]$
6. $[5, 2, 3, 4, 1]$
7. $[5, 3, 4, 1, 2]$
8. $[5, 4, 1, 2, 3]$
9. $[5, 1, 2, 3, 4]$
10. $[5, 2, 3, 4, 1] \Rightarrow A = 5, B = 2$.

详细考虑第一个测试用例的全部 10 步：

1. $[1, 2, 3, 4, 5]$ — 在第一次操作中，$A$ 和 $B$ 分别为 $1$ 和 $2$。
   因此，将 $2$ 插入双端队列（deque）的前端，将 $1$ 插入双端队列的尾端。
   得到双端队列的当前状态为：$[2, 3, 4, 5, 1]$。
2. $[2, 3, 4, 5, 1] \Rightarrow A = 2, B = 3$。
3. $[3, 4, 5, 1, 2]$
4. $[4, 5, 1, 2, 3]$
5. $[5, 1, 2, 3, 4]$
6. $[5, 2, 3, 4, 1]$
7. $[5, 3, 4, 1, 2]$
8. $[5, 4, 1, 2, 3]$
9. $[5, 1, 2, 3, 4]$
10. $[5, 2, 3, 4, 1] \Rightarrow A = 5, B = 2$。