A. Валера и дек
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно на курсе по алгоритмам и структурам данных Валера научился пользоваться деком. Он построил дек, заполненный $$$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$$$ для каждого из запросов нужно вывести в том порядке, в котором они будут вытащены из дека.

Дек — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов.

Входные данные

Первая строка содержит два целых числа $$$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}$$$).

Выходные данные

Для каждого вопроса преподавателя выведите два числа $$$A$$$ и $$$B$$$ — числа, которые вытащит Валера из дека на $$$m_j$$$-й операции.

Примеры
Входные данные
5 3
1 2 3 4 5
1
2
10
Выходные данные
1 2
2 3
5 2
Входные данные
2 0
0 0
Выходные данные
Примечание
     Рассмотрим все 10 шагов для первого теста подробно:
  1.  $$$[1, 2, 3, 4, 5]$$$ — на первой операции $$$A$$$ и $$$B$$$ равны соответственно $$$1$$$ и $$$2$$$.
    Значит, $$$2$$$ мы запишем в начало дека, а $$$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$$$.