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.*;
import java.util.Scanner;
import java.math.*;
import java.lang.StringBuilder;

public class contest
{
   public static void main(String[] args)
   {
      Scanner scan = new Scanner(System.in);
      
      int n = scan.nextInt();
      int q = scan.nextInt();
      int queue[] = new int[n];
      int queue1[] = new int[n];
      int queue2[] = new int[n];
      int start = 0;
      int queueOn = 0;
      for (int i = 0; i < n; i++)
      {
         queue1[i] = scan.nextInt();
         queue[i] = queue1[i];
      }
      long ji = 1l;
      for (int i = 0; i < q; i++)
      {
         long qnum = scan.nextLong();
         if (qnum < ji)//= n && ji > n)
         {
            ji = 1;
            start = 0;
            queueOn = 0;
            for (int z = 0; z < n; z++)
            {
               queue[z] = queue1[z];
            }
         }
         if (ji <= n)
         {
            for (long j = ji; j < qnum && j <= n; j++)
            {
               if (queue[start] > queue[(start + 1) % n])
               {
                  int temp = queue[start];
                  queue[start] = queue[(start + 1) % n];
                  queue[(start + 1) % n] = temp;
               }
               start++;
               start %= n;
            }
            ji = qnum;
            if (qnum <= n)
            {
               System.out.println(queue[start] + " " + queue[(start + 1) % n]);
            }
            else
            {
               ji = n + 1;
               if (queueOn == 0)
               {
                  for (int k = 0; k < n; k++)
                  {
                     queue2[k] = queue[(k + start) % n];
                  }
                  queueOn = 1;
               }
               System.out.print(queue2[0] + " ");
               System.out.println(queue2[(int) ((qnum - ji + n * 10 - 10) % (n - 1)) + 1]);
            }
         }
         else
         {
            if (queueOn == 0)
            {
               for (int k = 0; k < n; k++)
               {
                  queue2[k] = queue[(k + start) % n];
               }
               queueOn = 1;
            }
            System.out.print(queue2[0] + " ");
            System.out.println(queue2[(int) ((qnum - ji + n * 10 - 10) % (n - 1)) + 1]);
         }
      }
   }
   
   public static boolean isPandigital(int num)
   {
      return true;
   }
}
   
   /*private static int N;
   private static int M;
   
   public static void main(String[] args)
   {
      Scanner scan = new Scanner(System.in);
      N = scan.nextInt();
      M = scan.nextInt();
      
      LineWrapper lineWrapper = new LineWrapper();
      Line line = new Line(scan.nextInt(), scan.nextInt());
      
      lineWrapper.insert(new Line(line));
      for (int i = 1; i < M; i++)
      {
         lineWrapper.insert(new Line(scan.nextInt(), scan.nextInt()));
      }
      lineWrapper.sort();
      
      String comp = lineWrapper.toString();
      
      ArrayList<Integer> possible = new ArrayList<Integer>();
      
      int adder = 1 + N % 2;
      possible.add(0);
      possible.add(1);
      if (N % 2 == 0)
      {
         possible.add(2);
      }
      for (int i = 3; i < N / 2 + 1; i += adder)
      {
         if (N % i == 0)
         {
            possible.add(i);
         }
      }
      
      int i = 0;
      int j;
      int count = 0;
      
      do
      {
         j = 0;
         do
         {
            if (count > possible.size() - 2)
            {
               System.out.print("No");
               System.exit(0);
            }
            line.rotate(possible.get(count + 1) - possible.get(count) - 1);
            j += possible.get(count + 1) - possible.get(count);
            count++;
         } while (!lineWrapper.contains(line));
         
         lineWrapper.rotate(j - 1);
         line.rotate(j - 1);
         i += j;
      } while (!comp.equals(lineWrapper.toString()));
      
      int incr = i;
      i += incr;
      
      if (i > N)
      {
         System.out.print("No");
         System.exit(0);
      }
      for (; i < incr * 3 && i < N / 2 + 1; i += incr)
      {
         lineWrapper.rotate(incr - 1);
         
         if (!comp.equals(lineWrapper.toString()))
         {
            System.out.print("No");
            System.exit(0);
         }
      }
      System.out.print("Yes");
   }
   public static class LineWrapper
   {
      public ArrayList<Line> list;
      
      public LineWrapper()
      {
         list = new ArrayList<Line>();
      }
      
      public void insert(Line line)
      {
         list.add(line);
      }
      
      public void sort()
      {
         Collections.sort(list);
      }
      
      public void rotate(int incr)
      {
         for (Line line: list)
         {
            line.rotate(incr);
         }
         Collections.sort(list);
      }
      
      public boolean contains(Line line)
      {
         int left = 0;
         int right = M - 1;
         int mid = right / 2;
         int temp;
         while (right - left > 1)
         {
            temp = line.compareTo(list.get(mid));
            if (temp < 0)
            {
               right = mid;
            }
            else if (temp > 0)
            {
               left = mid;
            }
            else
            {
               return true;
            }
            mid = (left + right) / 2;
         }
         if (line.compareTo(list.get(right)) == 0 ||
             line.compareTo(list.get(left)) == 0)
         {
            return true;
         }
         return false;
      }
      
      public String toString()
      {
         StringBuilder s = new StringBuilder("");
         for (Line line: list)
         {
            s.append(line.toString());
         }
         return s.toString();
      }
   }
   public static class Line implements Comparable<Line>
   {
      private int a;
      private int b;
      
      public Line(int ain, int bin)
      {
         a = (ain < bin) ? ain : bin;
         b = (ain < bin) ? bin : ain;
      }
      
      public Line(Line line)
      {
         a = line.getA();
         b = line.getB();
      }
      
      public int getA()
      {
         return a;
      }
      
      public int getB()
      {
         return b;
      }
      
      public void rotate(int incr)
      {
         a = ((a + incr) % N) + 1;
         b = ((b + incr) % N) + 1;
         if (a > b)
         {
            int temp = a;
            a = b;
            b = temp;
         }
      }
      
      public String toString()
      {
         return "" + a + b;
      }
      
      @Override
      public int compareTo(Line line)
      {
         if (a < line.getA())
         {
            return -1;
         }
         if (a > line.getA())
         {
            return 1;
         }
         if (b < line.getB())
         {
            return -1;
         }
         if (b > line.getB())
         {
            return 1;
         }
         return 0;
      }
   }
}
      
/*   
      int A = scan.nextInt();
      int B = scan.nextInt();
      int As[];
      int Bs[];
      //0 = n^2 + n - 2(A + B)
      int N = (int) (-1.0 / 2 + 2 * Math.sqrt(1.0 / 16 + (A + B) / 2.0));
      if (B == 0)
      {
         int i = 0;
         while (A > 0 && N > i)
         {
            A -= (N - i);
            i++;
         }
         As = new int[i];
         for (int j = 0; j < i; j++)
         {
            As[j] = N - j;
         }
         System.out.println(i);
         for (int j = 0; j < i; j++)
         {
            System.out.print(As[j] + " ");
         }
         System.out.println("\n0");
      }
      else if (A == 0)
      {
         int i = 0;
         while (B > 0 && N > i)
         {
            B -= (N - i);
            i++;
         }
         Bs = new int[i];
         for (int j = 0; j < i; j++)
         {
            Bs[j] = N - j;
         }
         System.out.println("0\n");
         System.out.println(i);
         for (int j = 0; j < i; j++)
         {
            System.out.print(Bs[j] + " ");
         }
      }
      else if (A <= B)
      {
         int i = 0;
         while (A > N - i)
         {
            A -= (N - i);
            i++;
         }
         As = new int[i + 1];
         for (int j = 0; j < i; j++)
         {
            As[j] = N - j;
         }
         As[i] = A;
         Bs = new int[N - i - 1];
         int k = 0;
         for (int j = (i == 0) ? N : (As[i - 1] - 1); j > 0 && (k < N - i - 1); j--)
         {
            if (j != As[i])
            {
               Bs[k] = j;
               k++;
            }
         }
         System.out.println(i + 1);
         for (int j = 0; j < i + 1; j++)
         {
            System.out.print(As[j] + " ");
         }
         System.out.println("\n" + (N - i - 1));
         for (int j = 0; j < N - i - 1; j++)
         {
            System.out.print(Bs[j] + " ");
         }
      }
      else
      {
         int i = 0;
         while (B > N - i)
         {
            B -= (N - i);
            i++;
         }
         Bs = new int[i + 1];
         for (int j = 0; j < i; j++)
         {
            Bs[j] = N - j;
         }
         Bs[i] = B;
         As = new int[N - i - 1];
         int k = 0;
         for (int j = (i == 0) ? N : (Bs[i - 1] - 1); j > 0 && (k < N - i - 1); j--)
         {
            if (j != Bs[i])
            {
               As[k] = j;
               k++;
            }
         }
         System.out.println(N - i - 1);
         for (int j = 0; j < N - i - 1; j++)
         {
            System.out.print(As[j] + " ");
         }
         System.out.println("\n" + (i + 1));
         for (int j = 0; j < i + 1; j++)
         {
            System.out.print(Bs[j] + " ");
         }
      }
   }
}
      
      /*int N = scan.nextInt();
      int A[] = new int[N - 1];
      int B[] = new int[N - 1];
      int T[] = new int[N];
      for (int i = 0; i < N - 1; i++)
      {
         A[i] = scan.nextInt();
      }
      for (int i = 0; i < N - 1; i++)
      {
         B[i] = scan.nextInt();
      }
      for (int i = 0; i < N - 1; i++)
      {
         while ((T[i] | T[i + 1]) != A[i] ||
                (T[i] & T[i + 1]) != B[i])
         {
            if (T[i + 1] < 3)
            {
               T[i + 1]++;
            }
            else if (T[i] >= 3)
            {
               if (i != 0)
               {
                  T[i - 1]++;
                  T[i] = 0;
                  T[i + 1] = 0;
                  i -= 2;
                  break;
               }
               System.out.print("NO");
               System.exit(0);
            }
            else
            {
               T[i]++;
               T[i + 1] = 0;
               if (i != 0)
               {
                  i -= 2;
                  break;
               }
            }
         }
      }
      System.out.println("YES");
      for (int i = 0; i < N - 1; i++)
      {
         System.out.print(T[i] + " ");
      }
      System.out.print(T[N - 1]);
   }
}*/