James and Edward are playing a game! They lay out 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 -most side, where is equal to left for James and right for Edward.
First line, two integers and , denoting the number of cards and the number of times Jessica chooses a breaking point respectively.
Second line, space separated integers , denoting the value of each card.
Next lines, one integer , specifying the index of the breaking point.
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.
For all subtasks:
Subtask 1 [30%]
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 as the breaking point, meaning the maximum element on the left side of the breaking point is with index 2, and the right side is with index 4.
For the second query, Jessica chooses index as the breaking point, meaning the maximum element on the left side of the breaking point is with index 3, and the right side is 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, and both have the maximum value, however, for James, is closer to the left side of the array. Similarly, and both have the maximum value, but for Edward, is closer to the right side of the array.
The second query is a similar case.