The Detective's Game

medium

The great detective Sherlock Holmes has discovered a peculiar cipher machine at the scene of a mysterious crime. The machine contains a double-ended sequence holder with n number cards, where the i-th card shows the number ai a_i .

Holmes has deduced that the machine operates on a specific algorithm:

  • In each operation cycle, the machine extracts the first two leftmost cards A A and B B .
  • If A>B A > B , it places A A at the front and B B at the back.
  • Otherwise, it places B B at the front and A A at the back.

Holmes finds a ledger with q q timestamps. Each timestamp mj m_j represents a critical moment in the criminal's plan. To decode the hidden message, Holmes must determine which two cards would be extracted at the start of the mj m_j -th operation cycle.

Input Format:

The first line contains two integers n n and q q (2≤n≤105, 0≤q≤3×105)(2 \leq n \leq 10^5, \ 0 \leq q \leq 3 \times 10^5) — the number of cards in the sequence and the number of timestamps. The second line contains n n integers a1,a2,…,an a_1, a_2, \ldots, a_n (0≤ai≤109)\left(0 \leq a_i \leq 10^9\right) — the initial card sequence. The next q q lines contain one integer each, mj m_j (1≤mj≤1018)\left(1 \leq m_j \leq 10^{18}\right).

Output Format:

For each timestamp, output two numbers A A and B B — the numbers on the cards that would be extracted at the start of the mj m_j -th operation cycle.

Examples:

Example 1:

Input:

5 3
1 2 3 4 5
1
2
10

Output:

1 2
2 3
5 2

Code

Loading Editor...