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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Deque;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author caoash
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CValeriyAndDeque solver = new CValeriyAndDeque();
        solver.solve(1, in, out);
        out.close();
    }

    static class CValeriyAndDeque {
        public void solve(int testNumber, FastScanner br, PrintWriter pw) {
            int n = br.nextInt();
            int q = br.nextInt();
            int[] a = br.nextIntArray(n);
            int max = 0;
            for (int i = 0; i < a.length; i++) max = Math.max(max, a[i]);
            Deque<Integer> newA = new LinkedList<>();
            for (int i = 0; i < a.length; i++) {
                newA.add(a[i]);
            }
            Pair<Integer, Integer>[] ret = new Pair[n];
            for (int i = 0; i < n - 1; i++) {
                int v1 = newA.pollFirst();
                int v2 = newA.pollFirst();
                ret[i] = new Pair(v1, v2);
                if (v1 > v2) {
                    newA.addFirst(v1);
                    newA.addLast(v2);
                } else {
                    newA.addLast(v1);
                    newA.addFirst(v2);
                }
            }
            int[] orderLul = new int[n - 1];
            newA.pollFirst();
            for (int i = 0; i < n - 1; i++) {
                orderLul[i] = newA.pollFirst();
            }
            for (int i = 0; i < q; i++) {
                long qi = br.nextLong();
                if (qi < n) {
                    Pair p = ret[(int) (qi - 1)];
                    pw.println(p.f + " " + p.s);
                } else {
                    int ind = (int) (qi % (n - 1));
                    if (ind == 0) {
                        ind = n - 2;
                    } else {
                        ind--;
                    }
                    pw.println(max + " " + orderLul[ind]);
                }
            }
            pw.close();
        }

        public class Pair<U, V> implements Comparable<Pair<U, V>> {
            public final U f;
            public final V s;

            public Pair(U first, V second) {
                this.f = first;
                this.s = second;
            }

            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()) {
                    return false;
                }

                Pair pair = (Pair) o;

                return !(f != null ? !f.equals(pair.f) : pair.f != null) &&
                        !(s != null ? !s.equals(pair.s) : pair.s != null);
            }

            public int hashCode() {
                int result = f != null ? f.hashCode() : 0;
                result = 31 * result + (s != null ? s.hashCode() : 0);
                return result;
            }

            public String toString() {
                return "(" + f + "," + s + ")";
            }

            public int compareTo(Pair<U, V> o) {
                int value = ((Comparable<U>) f).compareTo(o.f);
                if (value != 0) {
                    return value;
                }
                return ((Comparable<V>) s).compareTo(o.s);
            }

        }

    }

    static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastScanner.SpaceCharFilter filter;

        public FastScanner(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        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 long nextLong() {
            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 boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; ++i) array[i] = nextInt();
            return array;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

