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.io.*;
import java.util.*;

public class Main {

    private static int MOD = 1000000007;

    public static void main(String[] args) throws Exception {
//        InputStream inS = System.in;
//        InputReader sc = new InputReader(inS);
        Helpers helpers = new Helpers();
        PrintStream out = System.out;
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), q = sc.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int[][] ans = new int[n+1][2];


        ans[0][0] = 0; ans[0][1] = 0;
        ans[1][0] = arr[0];ans[1][1] = arr[1];

        int max = Math.max(arr[0], arr[1]);
        for (int i = 2; i < ans.length - 1; i++) {
            ans[i][0] = max;
            ans[i][1] = arr[i];
            max = Math.max(max, arr[i]);
        }

        ans[n][0] = max; ans[n][1] = Math.min(ans[1][0], ans[1][1]);

        for (int i = 0; i < q; i++) {
            long que = sc.nextLong();
            if (que <= n) {
                out.println(ans[(int)que][0] + " " + ans[(int)que][1]);
            } else {
                long index = 0;
                if (que % (n-1) == 0) {
                    index = n-1;
                } else {
                    index = que % (n-1);
                }

                out.println(max + " " + (Math.min(ans[(int)index][0], ans[(int)index][1])));
            }
        }
        out.close();
    }

    private static long getProduct(int[] arr) {
        long product = 1;
        for (int i = 0; i < arr.length; i++) {
            product *= arr[i];
        }

        return product;
    }

    static int lis(int arr[], int n) {
        int result = 0;
        int[] lis = new int[n];

        for (int i = 0; i < n; i++) {
            lis[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (result < lis[i]) {
                result = lis[i];
            }
        }

        return result;
    }


    public static void takeIntInput(Scanner sc, long[] arr) {
        for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextLong();
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

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

    }

    static class Helpers {
        public  boolean less(Comparable a, Comparable b) {
            return a.compareTo(b) < 0;
        }

        public  boolean less(Comparator c, Object a, Object b) {
            return c.compare(a, b) < 0;
        }

        public  void exch(Object[] a, int i, int j) {
            Object swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }

        public  void main(String[] args) {
            Scanner sc = new Scanner(System.in);

            int n = sc.nextInt();
            while (n > 0) {
                System.out.print('(');
                n--;
            }
        }
        public  boolean isSorted(Comparable[] a) {
            return isSorted(a, 0, a.length-1);
        }

        /**
         *
         * @param a
         * @param start lie b/w 0 and length - 1
         * @param end lie b/w 0 and length - 1
         * @return if sorted b/w start and end indices
         */
        public  boolean isSorted(Comparable[] a, int start, int end) {
            for (int i = start ; i < end ; i++) {
                if (!less(a[i], a[i+1])) {
                    return false;
                }
            }

            return true;
        }

        public  boolean isSorted(Object[] a, int start, int end, Comparator c) {
            for (int i = start ; i < end ; i++) {
                if (!less(c, a[i], a[i+1])) {
                    return false;
                }
            }

            return true;
        }

        public  void copy(Object[] from, Object[] to, int lo, int hi) {
            for (int i = lo; i <= hi; i++) {
                to[i] = from[i];
            }
        }

        public  void display(Object[] a, int from, int to) {
            for (int i = from; i <= to; i++) {
                System.out.print(a[i] +  " ");
            }

            System.out.println();
        }

        public  void display(int[] a, int from, int to) {
            for (int i = from; i <= to; i++) {
                System.out.print(a[i] +  " ");
            }

            System.out.println();
        }

        public  String display(List<Integer> arr) {
            StringBuilder sb = new StringBuilder();
            for (Integer i : arr) {
                sb.append(i);
                sb.append(" ");
            }
            return sb.toString();
        }

        public  void display(char[] a, int from, int to) {
            for (int i = from; i <= to; i++) {
                System.out.print(a[i] +  " ");
            }

            System.out.println();
        }

        public  void takeIntInput(Scanner sc, Integer[] arr) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
        }

        public  void takeIntInput(Main.InputReader sc, int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
        }

        public  int getMax(int[] arr) {
            int max = Integer.MIN_VALUE;

            for (int i = 0; i < arr.length; i++) {
                max = Math.max(max, arr[i]);
            }

            return max;
        }

        public  void takeIntInput(Scanner sc, int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
        }

        public  int[] toArray(ArrayList<Integer> al) {
            int[] ret = new int[al.size()];
            for (int i = 0 ; i < al.size() ; i++) {
                ret[i] = al.get(i);
            }

            return ret;
        }

        public  boolean isLeapYear(int year) {
            return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
        }
    }

}
