James and Edward are playing a game! They lay out $N$ cards in a straight line, and choose a breaking point. James chooses a card on the left side of the breaking point, and Edward chooses a card on the right side of the breaking point. Then they compare their card values to see whose card value is greater.

However, since Edward is just too good due to his massive brain, James has decided that Jessica will choose the breaking point, and they will see who is faster at choosing the maximum element on their respective side. Also, just for insurance, he has asked you to make a program that will tell him which card he and Edward will choose, help James!

Note: Both Edward and James may not choose the breaking point as their chosen card. In addition, if there are ties, break them by choosing the card with index that is the $f$-most side, where $f$ is equal to left for James and right for Edward.

Input Specification

First line, two integers $N$ and $Q$, denoting the number of cards and the number of times Jessica chooses a breaking point respectively.

Second line, $N$ space separated integers $a_i$, denoting the value of each card.

Next $Q$ lines, one integer $x$, specifying the index of the breaking point.

Output Specification

For each query, output 2 space separated integers, the index of the card that James and Edward will choose respectively, given that they both will try their best to win.

Constraints

For all subtasks:

$5\le N\le {10}^6$

$1\le Q\le {10}^6$

$2\le x\le N-1$

$-{10}^9\le a_i\le {10}^9$

Subtask 1 [30%]

$5\le N\le {10}^3$

$1\le Q\le {10}^3$

Subtask 2 [70%]

No additional constraints.

Sample Input 1

5 2
1 2 3 4 -5
3
4

Sample Output 1

2 4
3 5

Sample Explanation 1

For the first query, Jessica chooses index $3$ as the breaking point, meaning the maximum element on the left side of the breaking point is $2$ with index 2, and the right side is $4$ with index 4.

For the second query, Jessica chooses index $4$ as the breaking point, meaning the maximum element on the left side of the breaking point is $3$ with index 3, and the right side is $-5$ with index 5.

Sample Input 2

5 2
2 2 2 6 6
3
4

Sample Output 2

1 5
1 5

Sample Explanation 2

For the first query, $a_1$ and $a_2$ both have the maximum value, however, for James, $a_1$ is closer to the left side of the array. Similarly, $a_4$ and $a_5$ both have the maximum value, but for Edward, $a_5$ is closer to the right side of the array.

The second query is a similar case.