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 java.util.*;
import java.io.*;
 
public class Mamo {
    static long mod=1000000007;
    static Reader in=new Reader();
    static List<Integer >G[];
    static long a[],p[],xp[],xv[];
    static StringBuilder Sd=new StringBuilder(),Sl=new StringBuilder();
    public static void main(String [] args) {
    	//Dir by MohammedElkady
    	int n=in.nextInt(),q=in.nextInt(),po=0,max=0;
    	ArrayList<Integer> a=new ArrayList();
    	
    	for(int i=0;i<n;i++) {
    		a.add(in.nextInt());
    		if(a.get(i)>max) {max=a.get(i);po=i;}}
    	String S[]=new String [n];
    	for(int i=0;i<po;i++) {
    		S[i]=String.valueOf(a.get(0)+" "+a.get(1));
    		if(a.get(0)>a.get(1)) {
    			int x=a.remove(1);
                a.add(x);
    		}
    		else {	int x=a.remove(0);
            a.add(x);}
    	}
    	a.remove(0);
    	while(q-->0) {
    		long v=in.l();
    		if(v>po) {
    			out.append(max+" ");
    			v-=po;
    			v--;
    			v%=a.size();
    			
    			out.append(a.get((int)(v%a.size()))+"\n");
    		}
    		else {out.append(S[(int)v-1]+"\n");}
    	}
    	out.close();
    }
    
    static long ans=0L;
    static boolean v[];
    static ArrayList<Integer>res;
    static  Queue <Integer> pop;
    static  Stack <Integer>rem;
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static long gcd(long g,long x){if(x<1)return g;else return gcd(x,g%x);}  
    static class Reader 
    { 
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public Reader() { this(System.in); }public Reader(InputStream is) { mIs = is;} 
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];} 
        public String nextLine(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isEndOfLine(c));return res.toString() ;} 
        public String s(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isSpaceChar(c));return res.toString();} 
        public long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;} 
        public int nextInt(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;} 
        public double d() throws IOException {return Double.parseDouble(s()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
        public int[] arr(int n){int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = nextInt();}return ret;}
    }
}

class stree{
	public stree(int n,long a[]) {
		this.a=a;
		seg=new long[n*4];
		lazy=new long[n*4];
		build(1,0,n-1);
	}
	long seg[], a[],lazy[];
	    void check(int p,int s,int e) {
	        if(lazy[p]!=0) {
	            seg[p] += lazy[p];
	            if(s!=e) {
	                lazy[2*p] += lazy[p];
	                lazy[2*p+1] += lazy[p];
	            }
	            lazy[p] = 0;
	        }
	    }
	    
	     void build(int p,int s,int e) {
	        check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = a[s];
	            return;
	        }
	        
	        build(2*p,s,(s+e)/2);
	        build(2*p+1,(s+e)/2+1,e);
	        
	        seg[p] = Math.max(seg[2*p], seg[2*p+1]);
	    }
	    
	   void update(int p,int s,int e,int i,int v) {
	        check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = v;
	            return;
	        }
	        
	        if(i<=(s+e)/2) update(2*p,s,(s+e)/2,i,v);
	        else update(2*p+1,(s+e)/2+1,e,i,v);
	        
	        seg[p] = Math.max(seg[2*p],seg[2*p+1]);
	    }
	    
	     void update(int p,int s,int e,int a,int b,int v) {
	        check(p,s,e);
	        
	        if(s>=a && e<=b) {
	            seg[p] += v;
	            
	            if(s!=e) {
	                lazy[2*p] += v;
	                lazy[2*p+1] += v;
	            }
	            
	            return;
	        }
	        
	        if(s>b || e<a)
	            return;
	        
	        update(2*p,s,(s+e)/2,a,b,v);
	        update(2*p+1,(s+e)/2+1,e,a,b,v);
	        
	        seg[p] = Math.max(seg[2*p],seg[2*p+1]);
	    }
    
 
    
    long get(int p,int s,int e,int a,int b) {
        if(s>=a && e<=b)
            return seg[p];
        
        if(s>b || e<a)
            return Long.MIN_VALUE; 
        
        return Math.max(get(2*p,s,(s+e)/2,a,b), get(2*p+1,(s+e)/2+1,e,a,b));
    }
}
class node implements Comparable<node>{
int a, b;
node(int tt,int ll){
a=tt;b=ll;
}
    @Override
    public int compareTo(node o) {
    return b-o.b;    
    }
}
class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
}
 
class Sorting{
 
 public static long[] bucketSort(long[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 long high = array[0];
 
 long low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Long> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
}