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. 
//package Contest569;

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class mainC {
    public static PrintWriter out = new PrintWriter(System.out);
    public static FastScanner enter = new FastScanner(System.in);
    public static pair[] Q;
    public static long[] arr;
    public static void main(String[] args) throws IOException {
        int n=enter.nextInt();
        int q=enter.nextInt();
        arr=new long[n];
        Q=new pair[q];
        for (int i = 0; i <n ; i++) {
            arr[i]=enter.nextLong();
        }
        for (int i = 0; i <q ; i++) {
            Q[i]=new pair(i,enter.nextLong()-1);
        }
        sortMergeNoRecursive(Q,0,q,pair.class,pair::compareTo);
        long f_max=-1;
        int ind=-1;
        for (int i = 0; i <n ; i++) {
            if(arr[i]>f_max){
                ind=i;
                f_max=arr[i];
            }
        }
        LinkedList<Long> dec=new LinkedList<>();
        for (int i = 0; i <n ; i++) {
            dec.addLast(arr[i]);
        }
        long mass1[]=new long[ind+1];
        long mass2[]=new long[ind+1];
        mass1[0]=arr[0];
        mass2[0]=arr[1];
        for (int i = 1; i <=ind ; i++) {
            long f=dec.pollFirst();
            long s=dec.peekFirst();
            if(f>=s){
                s=dec.pollFirst();
                dec.addFirst(f);
                dec.addLast(s);
            }
            else{
                dec.addLast(f);
            }
            mass1[i]=dec.pollFirst();
            mass2[i]=dec.peekFirst();
            dec.addFirst(mass1[i]);
        }
        /*System.out.println(dec);
        System.out.println(ind);*/
        long ans1[] =new long[q];
        long ans2[] =new long[q];
        Iterator<Long> iter=dec.iterator();
        long last_mass[]=new long[n];
       int j=0;
        while(iter.hasNext())
        {
            last_mass[j]=iter.next();
            j++;
        }

        for (int i = 0; i <q ; i++) {
            if(Q[i].zap>=ind+1){
                ans1[Q[i].pos]=f_max;
                ans2[Q[i].pos]=last_mass[1+(int)((Q[i].zap-ind)%(n-1))];
            }
            else{
                ans1[Q[i].pos]=mass1[(int)Q[i].zap];
                ans2[Q[i].pos]=mass2[(int)Q[i].zap];
            }
        }

        for (int i = 0; i <q ; i++) {
            out.println(ans1[i]+" "+ans2[i]);
        }
        out.close();
    }

    public static <T>  void sortMergeNoRecursive(T[] arr, int first, int last, Class<T> c, Comparator<T> comparator) {
        int len = last;
        int n = 1; // кратность сравнений (сравнивать по 1-му элем., 2-м ...)
        int shift; // сдвиг в перебираемом массиве
        int two_size; // количество элементов для 2-го массива
        T[] arr2;
        while (n < len) {
            shift = first;
            while (shift < len) {
                if (shift + n >= len) break;
                two_size = (shift + n * 2 > len) ? (len - (shift + n)) : n;
                arr2 = merge(Arrays.copyOfRange(arr, shift, shift + n),
                        Arrays.copyOfRange(arr, shift + n, shift + n + two_size),c,comparator);
                for (int i = 0; i < n + two_size; ++i)
                    arr[shift + i] = arr2[i]; // замена на отсортированное
                shift += n * 2;
            }
            n *= 2;
        }
    }

    public static <T> T[] merge(T[] arr_1, T[] arr_2,Class<T> c , Comparator<T> comparator) {
        int len_1 = arr_1.length, len_2 = arr_2.length;
        int a = 0, b = 0, len = len_1 + len_2; // a, b - счетчики в массивах
        //T[] result = new <>[len];
        T[] result=(T[]) Array.newInstance(c,len);


        for (int i = 0; i < len; i++) {
            if (b < len_2 && a < len_1) {
                if (comparator.compare(arr_1[a], arr_2[b]) > 0) result[i] = arr_2[b++];
                else result[i] = arr_1[a++];
            } else if (b < len_2) {
                result[i] = arr_2[b++];
            } else {
                result[i] = arr_1[a++];
            }
        }
        return result;
    }


    static class pair implements Comparable<pair>{
        int pos;
        long zap;

        public pair(int pos, long zap) {
            this.pos = pos;
            this.zap = zap;
        }

        @Override
        public int compareTo(pair o) {
            return Long.compare(zap,o.zap);
        }
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer stok;

        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        String next() throws IOException {
            while (stok == null || !stok.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) {
                    return null;
                }
                stok = new StringTokenizer(s);
            }
            return stok.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        char nextChar() throws IOException {
            return (char) (br.read());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }
    }
}

