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, …, 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, …, 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.

Input

The first line contains two integers n and q (2 ≤ n ≤ 10^5, 0 ≤ q ≤ 3 ⋅ 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 ≤ a_i ≤ 10^9) — the deque element in i-th position. The next q lines contain one number each, meaning m_j (1 ≤ m_j ≤ 10^{18}).

Output

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.

Examples

Input


5 3
1 2 3 4 5
1
2
10


Output


1 2
2 3
5 2


Input


2 0
0 0


Output

Note

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] ⇒ 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] ⇒ A = 5, B = 2. 
#import resource
import sys
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
#import threading
#threading.Thread(target=main).start()
#threading.stack_size(2**26)
#sys.setrecursionlimit(10**6)
mod=(10**9)+7
#fact=[1]
#for i in range(1,100001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*100001
#ifact[100000]=pow(fact[100000],mod-2,mod)
#for i in range(100000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import collections
import math
import heapq
from random import randint as rn
from Queue import Queue as Q
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def ain():
    return map(int,sin().split())
def sin():
    return stdin.readline().strip()
def GCD(x,y):
    while(y):
        x, y = y, x % y
    return x
def isprime(x):
    if(x==1):
        return False
    elif(x<4):
        return True
    for i in range(2,int(math.sqrt(x))+1):
        if(x%i==0):
            return False
    return True
"""**************************************************************************"""
n,q=ain()
a=ain()
g=max(a)
d=collections.deque(a)
f=0
an1=[]
while(d[0]!=g):
    f+=1
    x=d.popleft()
    y=d.popleft()
    an1.append(str(x)+" "+str(y))
    if(y==g):
        d.appendleft(y)
        d.append(x)
        break
    if(x<y):
        d.appendleft(y)
        d.append(x)
    else:
        d.appendleft(x)
        d.append(y)
r=[]
ans=[]
for i in range(n):
    r.append(str(d.popleft()))
for i in range(q):
    b=int(sin())
    if(b<=f):
        ans.append(an1[b-1])
    else:
        b-=f
        b-=1
        b%=(n-1)
        ans.append(r[0]+" "+r[b+1])
stdout.write("\n".join(ans))
