#include <bits/stdc++.h>
typedef struct link {
  int elemento;
  struct link *next;
} Link;
typedef struct list {
  Link *head;
  Link *tail;
  Link *curr;
  int cnt;
} List;
Link *create_link(int it, Link *nextval) {
  Link *n = (Link *)malloc(1 * sizeof(Link));
  n->elemento = it;
  n->next = nextval;
  return n;
}
Link *create_link_nulo(Link *nextval) {
  Link *n = (Link *)malloc(1 * sizeof(Link));
  n->next = nextval;
  return n;
}
List *create_list() {
  List *l = (List *)malloc(1 * sizeof(List));
  l->curr = l->tail = l->head = create_link_nulo(NULL);
  l->cnt = 0;
  return l;
}
void insert(List *l, int it) {
  l->curr->next = create_link(it, l->curr->next);
  if (l->tail == l->curr) l->tail = l->curr->next;
  l->cnt++;
}
void append(List *l, int it) {
  l->tail->next = create_link(it, NULL);
  l->tail = l->tail->next;
  l->cnt++;
}
void moveToStart(List *l) { l->curr = l->head; }
void moveToEnd(List *l) { l->curr = l->tail; }
void prev(List *l) {
  if (l->curr != l->head) {
    Link *temp = l->head;
    while (temp->next != l->curr) {
      temp = temp->next;
    }
    l->curr = temp;
  }
}
void next(List *l) {
  if (l->curr != l->tail) l->curr = l->curr->next;
}
int length(List *l) { return l->cnt; }
int currPos(List *l) {
  Link *temp = l->head;
  int i = 0;
  while (l->curr != temp) {
    temp = temp->next;
    i++;
  }
  return i;
}
void moveToPos(List *l, int pos) {
  if (pos >= 0 && pos < l->cnt) {
    l->curr = l->head;
    int i = 0;
    while (i < pos) {
      l->curr = l->curr->next;
      i++;
    }
  }
}
int getValue(List *l) {
  if (l->curr->next != NULL)
    return l->curr->next->elemento;
  else
    return 0;
}
int remover(List *l) {
  if (l->curr->next == NULL) return 0;
  Link *aux = l->curr->next;
  int it = l->curr->next->elemento;
  if (l->tail == l->curr->next) l->tail = l->curr;
  l->curr->next = l->curr->next->next;
  free(aux);
  l->cnt--;
  return it;
}
void clear(List *l) {
  int tam = l->cnt;
  int i;
  Link *aux;
  l->curr = l->head;
  for (i = 0; i < tam; i++) {
    remover(l);
  }
  l->cnt = 0;
  l->head->next = NULL;
  l->curr = l->head;
  l->tail = l->head;
}
int main(void) {
  int n, q, aux, max = 0, indexMax = 0;
  scanf("%d %d", &n, &q);
  List *a = create_list();
  for (int i = 0; i < n; i++) {
    scanf("%d", &aux);
    moveToEnd(a);
    insert(a, aux);
    if (aux > max) {
      max = aux;
      indexMax = i;
    }
  }
  long long int *m = (long long int *)malloc((q + 1) * sizeof(long long int));
  for (int i = 0; i < q; i++) {
    scanf("%lld", &m[i]);
  }
  long long int **ans = (long long int **)malloc((2) * sizeof(long long int *));
  ans[0] = (long long int *)malloc((indexMax + 1) * sizeof(long long int));
  ans[1] = (long long int *)malloc((indexMax + 1) * sizeof(long long int));
  for (int i = 0; i < indexMax; i++) {
    int A, B;
    moveToStart(a);
    A = remover(a);
    B = remover(a);
    ans[0][i] = A;
    ans[1][i] = B;
    if (A > B) {
      insert(a, A);
      moveToEnd(a);
      insert(a, B);
    } else {
      insert(a, B);
      moveToEnd(a);
      insert(a, A);
    }
  }
  moveToStart(a);
  next(a);
  int *b = (int *)malloc(n * sizeof(int));
  for (int i = 0; i < n - 1; i++) {
    b[i] = a->curr->next->elemento;
    next(a);
  }
  printf("\n");
  for (int i = 0; i < q; i++) {
    if (m[i] <= indexMax) {
      printf("%lld %lld\n", ans[0][m[i] - 1], ans[1][m[i] - 1]);
    } else {
      long long int index = (m[i] - indexMax - 1) % (n - 1);
      printf("%d %d\n", max, b[index]);
    }
  }
  clear(a);
  free(a->curr);
  free(a);
  free(m);
  free(ans[0]);
  free(ans[1]);
  free(ans);
  free(b);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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. 

### Response

```cpp
#include <bits/stdc++.h>
typedef struct link {
  int elemento;
  struct link *next;
} Link;
typedef struct list {
  Link *head;
  Link *tail;
  Link *curr;
  int cnt;
} List;
Link *create_link(int it, Link *nextval) {
  Link *n = (Link *)malloc(1 * sizeof(Link));
  n->elemento = it;
  n->next = nextval;
  return n;
}
Link *create_link_nulo(Link *nextval) {
  Link *n = (Link *)malloc(1 * sizeof(Link));
  n->next = nextval;
  return n;
}
List *create_list() {
  List *l = (List *)malloc(1 * sizeof(List));
  l->curr = l->tail = l->head = create_link_nulo(NULL);
  l->cnt = 0;
  return l;
}
void insert(List *l, int it) {
  l->curr->next = create_link(it, l->curr->next);
  if (l->tail == l->curr) l->tail = l->curr->next;
  l->cnt++;
}
void append(List *l, int it) {
  l->tail->next = create_link(it, NULL);
  l->tail = l->tail->next;
  l->cnt++;
}
void moveToStart(List *l) { l->curr = l->head; }
void moveToEnd(List *l) { l->curr = l->tail; }
void prev(List *l) {
  if (l->curr != l->head) {
    Link *temp = l->head;
    while (temp->next != l->curr) {
      temp = temp->next;
    }
    l->curr = temp;
  }
}
void next(List *l) {
  if (l->curr != l->tail) l->curr = l->curr->next;
}
int length(List *l) { return l->cnt; }
int currPos(List *l) {
  Link *temp = l->head;
  int i = 0;
  while (l->curr != temp) {
    temp = temp->next;
    i++;
  }
  return i;
}
void moveToPos(List *l, int pos) {
  if (pos >= 0 && pos < l->cnt) {
    l->curr = l->head;
    int i = 0;
    while (i < pos) {
      l->curr = l->curr->next;
      i++;
    }
  }
}
int getValue(List *l) {
  if (l->curr->next != NULL)
    return l->curr->next->elemento;
  else
    return 0;
}
int remover(List *l) {
  if (l->curr->next == NULL) return 0;
  Link *aux = l->curr->next;
  int it = l->curr->next->elemento;
  if (l->tail == l->curr->next) l->tail = l->curr;
  l->curr->next = l->curr->next->next;
  free(aux);
  l->cnt--;
  return it;
}
void clear(List *l) {
  int tam = l->cnt;
  int i;
  Link *aux;
  l->curr = l->head;
  for (i = 0; i < tam; i++) {
    remover(l);
  }
  l->cnt = 0;
  l->head->next = NULL;
  l->curr = l->head;
  l->tail = l->head;
}
int main(void) {
  int n, q, aux, max = 0, indexMax = 0;
  scanf("%d %d", &n, &q);
  List *a = create_list();
  for (int i = 0; i < n; i++) {
    scanf("%d", &aux);
    moveToEnd(a);
    insert(a, aux);
    if (aux > max) {
      max = aux;
      indexMax = i;
    }
  }
  long long int *m = (long long int *)malloc((q + 1) * sizeof(long long int));
  for (int i = 0; i < q; i++) {
    scanf("%lld", &m[i]);
  }
  long long int **ans = (long long int **)malloc((2) * sizeof(long long int *));
  ans[0] = (long long int *)malloc((indexMax + 1) * sizeof(long long int));
  ans[1] = (long long int *)malloc((indexMax + 1) * sizeof(long long int));
  for (int i = 0; i < indexMax; i++) {
    int A, B;
    moveToStart(a);
    A = remover(a);
    B = remover(a);
    ans[0][i] = A;
    ans[1][i] = B;
    if (A > B) {
      insert(a, A);
      moveToEnd(a);
      insert(a, B);
    } else {
      insert(a, B);
      moveToEnd(a);
      insert(a, A);
    }
  }
  moveToStart(a);
  next(a);
  int *b = (int *)malloc(n * sizeof(int));
  for (int i = 0; i < n - 1; i++) {
    b[i] = a->curr->next->elemento;
    next(a);
  }
  printf("\n");
  for (int i = 0; i < q; i++) {
    if (m[i] <= indexMax) {
      printf("%lld %lld\n", ans[0][m[i] - 1], ans[1][m[i] - 1]);
    } else {
      long long int index = (m[i] - indexMax - 1) % (n - 1);
      printf("%d %d\n", max, b[index]);
    }
  }
  clear(a);
  free(a->curr);
  free(a);
  free(m);
  free(ans[0]);
  free(ans[1]);
  free(ans);
  free(b);
  return 0;
}

```