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

import static java.lang.Integer.parseInt;

public class m {
  private static final boolean ONLINE_JUDGE = true; //System.getProperty("ONLINE_JUDGE") != null;

  public static void main(String[] args) {
    try (BufferedReader reader = ONLINE_JUDGE ? new BufferedReader(new InputStreamReader(System.in))
                                              : new BufferedReader(new FileReader("input"));
         Writer writer = ONLINE_JUDGE ? new OutputStreamWriter(System.out) : new FileWriter("output");
         PrintWriter printWriter = new PrintWriter(writer);) {
      Solver solver = new Solver(reader, printWriter);
      while (solver.solve());
    } catch (IOException e) {
      e.printStackTrace(System.err);
    }
  }

  static final class Solver {
    final BufferedReader in;
    final PrintWriter out;

    public Solver(BufferedReader reader, PrintWriter writer) {
      in = reader;
      out = writer;
    }

    boolean solve() throws IOException {
      String line = in.readLine();
      if (line == null) {
        return false;
      }
      if (line.isEmpty()) {
        return true;
      }
      StringTokenizer tok = new StringTokenizer(line);
      int n = Integer.parseInt(tok.nextToken());
      int q = Integer.parseInt(tok.nextToken());
      int[] a = new int[n];
      tok = new StringTokenizer(in.readLine());
      Deque<Integer> deque = new ArrayDeque<>();
      List<Integer> finalDeq = null;
      ArrayList<Pair> requests = new ArrayList<>();
      Map<Integer, Integer> ansA = new TreeMap<>();
      Map<Integer, Integer> ansB = new TreeMap<>();
      int maxVal = -1;
      int maxind = -1;
      for (int i = 0; i < n; ++i){
        a[i] = Integer.parseInt(tok.nextToken());
        deque.addLast(a[i]);
        if (maxVal < a[i]) {
          maxVal = a[i];
          maxind = i;
        }
      }

      for (int qq = 0; qq < q; ++qq) {
        long m = Long.parseLong(in.readLine());
        requests.add(new Pair(qq, m));
      }

      Collections.sort(requests,  (p1, p2) -> Long.compare(p1.value, p2.value));
      int lastPerm = 0;
      int lastA = -1;
      int lastB = -1;
      for (int i = 0; i < requests.size(); ++i) {
        Pair req  = requests.get(i);
        if (req.value <= maxind) {
          if (lastPerm == req.value) {
            ansA.put(req.index, lastA);
            ansB.put(req.index, lastB);
          } else while (lastPerm < req.value) {
            ++lastPerm;
            int A = deque.pollFirst();
            int B = deque.pollFirst();
            lastA = A;
            lastB = B;
            ansA.put(req.index, A);
            ansB.put(req.index, B);
            if (A > B) {
              deque.addFirst(A);
              deque.addLast(B);
            } else {
              deque.addFirst(B);
              deque.addLast(A);
            }
          }
          //debug("gagaga " + deque);
        } else {
          while (lastPerm < maxind) {
            ++lastPerm;
            int A = deque.pollFirst();
            int B = deque.pollFirst();
            ansA.put(req.index, A);
            ansB.put(req.index, B);
            if (A > B) {
              deque.addFirst(A);
              deque.addLast(B);
            } else {
              deque.addFirst(B);
              deque.addLast(A);
            }
          }
          if (finalDeq== null) {
            finalDeq = new ArrayList<>();
            for (Integer aa : deque) {
              finalDeq.add(aa);
            }
          }
          assert lastPerm == maxind;
          int left =(int) ((req.value - (1L +  maxind)) % ((long) (n - 1)));
          int b = finalDeq.get(1 + left);

          ansA.put(req.index, finalDeq.get(0));
          ansB.put(req.index, b);
        }
      }

      for (Integer key : ansA.keySet()) {
        int A = ansA.get(key);
        int B = ansB.get(key);
        out.println(A + " " + B);
      }
      //out.println();

      return true;
    }
  }

  static class Pair {
    int index;
    long value;

    public Pair(int a, long b) {index = a; value = b;}
    int getIndex() {return index;}
  }

  static void debug(String s) {
    System.out.println(s);
  }
}
