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. 
#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char* x) { cerr << '\"' << x << '\"'; }
void __print(const string& x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V>& x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T& x) {
  int f = 0;
  cerr << '{';
  for (auto& i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
template <typename T>
void print(vector<T> v) {
  for (T i : v) cout << i << " ";
  cout << '\n';
}
template <typename T>
void print(vector<vector<T>>& v) {
  for (vector<T>& vv : v) {
    for (T& i : vv) cout << i << " ";
    cout << '\n';
  }
}
template <typename T>
void read(vector<T>& v) {
  for (T& i : v) cin >> i;
}
template <typename T>
void read(T&& t) {
  cin >> t;
}
template <typename T, typename... Args>
void read(T&& t, Args&&... args) {
  cin >> t;
  read(forward<Args>(args)...);
}
template <typename T>
void print(T&& t) {
  cout << t << '\n';
}
template <typename T, typename... Args>
void print(T&& t, Args&&... args) {
  cout << t << " ";
  print(forward<Args>(args)...);
}
template <typename T>
vector<T>& operator--(vector<T>& v) {
  for (auto& i : v) --i;
  return v;
}
template <typename T>
vector<T>& operator++(vector<T>& v) {
  for (auto& i : v) ++i;
  return v;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& i : v) is >> i;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (auto& i : v) os << i << ' ';
  return os;
}
long double pie = 3.141592653589793238462643383279502884197169399;
long long mod = 1e9 + 7;
bool isprime(long long n) {
  if (n <= 1) {
    return false;
  }
  if (n <= 3) {
    return true;
  }
  if (n % 2 == 0 || n % 3 == 0) {
    return false;
  }
  for (long long i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) {
      return false;
    }
  }
  return true;
}
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}
long long modInverse(long long n, long long mod) {
  return binpow(n, mod - 2, mod);
}
long long comb(long long n, long long r, long long p, vector<long long>& fac) {
  if (r == 0 or n == r) return 1;
  if (r > n) return 0;
  return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) %
         p;
}
set<long long> divisors(long long n) {
  set<long long> s;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      s.insert(i);
      s.insert(n / i);
    }
  }
  return s;
}
set<int> primess;
void seive() {
  vector<int> is_prime(1e7 + 1, true);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i * i <= 1e7; i++) {
    if (is_prime[i]) {
      for (int j = i * i; j <= 1e7; j += i) is_prime[j] = false;
    }
  }
  for (int i = 2; i <= 1e7; i++) {
    if (is_prime[i]) {
      primess.insert(i);
    }
  }
}
long long add(long long a, long long b, long long mod) {
  a = a % mod;
  b = b % mod;
  return (((a + b) % mod) + mod) % mod;
}
long long mul(long long a, long long b, long long mod) {
  a = a % mod;
  b = b % mod;
  return (((a * b) % mod) + mod) % mod;
}
long long sub(long long a, long long b, long long mod) {
  a = a % mod;
  b = b % mod;
  return (((a - b) % mod) + mod) % mod;
}
map<long long, long long> primeFactors(long long n) {
  map<long long, long long> m;
  while (n % 2 == 0) {
    m[2]++;
    n = n / 2;
  }
  for (long long i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      m[i]++;
      n = n / i;
    }
  }
  if (n > 2) m[n]++;
  return m;
}
long long factorial(long long n, long long mod) {
  long long res = 1;
  for (long long i = 1; i <= n; i++) {
    res = mul(res, i, mod);
  }
  return res;
}
long long C(long long n, long long r) {
  long long res = 1;
  for (long long i = 0; i < r; i++) {
    res = res * (n - i) / (i + 1);
  }
  return res;
}
long long toint(string s) {
  long long num = 0;
  for (long long i = 0; i < s.size(); i++) {
    num = num * 10 + s[i] - '0';
  }
  return num;
}
long long sumstring(string s) {
  long long sum = 0;
  for (long long i = 0; i < s.size(); i++) {
    sum += (s[i] - '0');
  }
  return sum;
}
long long sumdigit(long long n) {
  long long sum = 0;
  while (n) {
    long long rem = n % 10;
    sum += rem;
    n /= 10;
  }
  return sum;
}
string tobinary(long long x) {
  string a;
  while (x > 0) {
    a += (x % 2) + '0';
    x /= 2;
  }
  reverse(begin(a), end(a));
  return a;
}
long long todecimal(string x) {
  long long sum = 0;
  long long n = x.size();
  long long j = 0;
  for (long long i = n - 1; i >= 0; i--) {
    if (x[i] == '1') {
      sum += (1LL << j);
    }
    j++;
  }
  return sum;
}
long long ceil(long long n, long long k) { return (n + k - 1) / k; }
bool ispalin(string s) {
  long long n = s.size();
  for (long long i = 0; i < n; i++) {
    if (s[i] != s[n - i - 1]) {
      return false;
    }
  }
  return true;
}
bool ispermutation(vector<long long> p) {
  sort(begin(p), end(p));
  for (long long i = 1; i <= p.size(); i++) {
    if (p[i - 1] != i) return false;
  }
  return true;
}
bool isperfect(long long x) {
  long long a = sqrtl(x);
  return a * a == x;
}
bool issubsequence(string t, string x) {
  long long j = 0;
  for (long long i = 0; i < x.size(); i++) {
    if (x[i] == t[j]) {
      j++;
    }
    if (j == t.size()) break;
  }
  return j == t.size();
}
long long power(long long base, long long exponent) {
  long long res = 1;
  while (exponent) {
    if (exponent & 1) {
      res = res * base;
    }
    base *= base;
    exponent >>= 1;
  }
  return res;
}
struct Cmp {
  bool operator()(const pair<long long, long long>& l,
                  const pair<long long, long long>& r) const {
    return l.second < r.second;
  }
};
bool comp(string s1, string s2) {
  for (long long i = 0; i < s1.size(); i++) {
    if (s1[i] == s2[i]) continue;
    return s1[i] < s2[i];
  }
  return false;
}
double area(double dX0, double dY0, double dX1, double dY1, double dX2,
            double dY2) {
  double dArea = ((dX1 - dX0) * (dY2 - dY0) - (dX2 - dX0) * (dY1 - dY0)) / 2.0;
  return (dArea > 0.0) ? dArea : -dArea;
}
long long C(long long n, long long r, long long mod) {
  long long ans = 1;
  if (n - r < r) r = n - r;
  for (long long i = n; i > n - r; i--) ans = mul(ans, i, mod);
  for (long long i = 1; i <= r; i++) ans = mul(ans, modInverse(i, mod), mod);
  return ans;
}
void solve() {
  long long n, m;
  cin >> n >> m;
  deque<long long> d;
  long long mx = 0;
  for (long long i = 0; i < n; i++) {
    long long x;
    cin >> x;
    d.push_back(x);
    mx = max(mx, x);
  }
  vector<pair<long long, long long>> q(m);
  for (long long i = 0; i < m; i++) {
    long long x;
    cin >> x;
    q[i].first = x;
    q[i].second = i;
  }
  sort(begin(q), end(q));
  vector<pair<long long, long long>> ans(m);
  long long i;
  long long left = -1;
  long long prev = 0;
  long long cycle = 0;
  for (i = 0; i < m; i++) {
    long long times = q[i].first - 1 - prev;
    while (times and d.front() != mx) {
      cycle++;
      long long a = d.front();
      d.pop_front();
      long long b = d.front();
      d.pop_front();
      if (a > b) {
        d.push_front(a);
        d.push_back(b);
      } else {
        d.push_front(b);
        d.push_back(a);
      }
      times -= 1;
    }
    if (d.front() == mx and times) {
      break;
    } else {
      long long first = d.front();
      d.pop_front();
      long long second = d.front();
      d.push_front(first);
      ans[q[i].second] = {first, second};
    }
    prev = q[i].first - 1;
  }
  d.pop_front();
  vector<long long> op;
  while (d.size()) {
    op.push_back(d.front());
    d.pop_front();
  }
  long long sz = op.size();
  for (; i < m; i++) {
    long long times = q[i].first - (cycle + 1);
    long long ind = times % sz;
    ans[q[i].second] = {mx, op[ind]};
  }
  for (auto i : ans) cout << i.first << ' ' << i.second << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}
