A. Valeriy and Deque
data structures; implementation
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: \([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, 3, 4, 5, 1] \Rightarrow A = 2, B = 3\). \([3, 4, 5, 1, 2]\) \([4, 5, 1, 2, 3]\) \([5, 1, 2, 3, 4]\) \([5, 2, 3, 4, 1]\) \([5, 3, 4, 1, 2]\) \([5, 4, 1, 2, 3]\) \([5, 1, 2, 3, 4]\) \([5, 2, 3, 4, 1] \Rightarrow A = 5, B = 2\).