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