D. Doubting Thomas
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ valuable artifacts arranged in a row, where the $$$i$$$-th artifact has a cost $$$c_i$$$. Thomas is planning on stealing some of the artifacts. He is going to iterate through each artifact in order, and steal any artifact whose cost is at least the $$$\operatorname{MEX}$$$ of the artifacts he has already stolen.

The $$$\operatorname{MEX}$$$ of a set of integers is defined as the smallest non-negative integer which does not occur in the set. For example, the $$$\operatorname{MEX}$$$ of $$$\{0, 1, 2, 4\}$$$ is $$$3$$$, and the $$$\operatorname{MEX}$$$ of $$$\{1, 4, 6, 8\}$$$ is $$$0$$$.

For example, if Thomas has previously stolen artifacts with costs of $$$\{1, 2, 1, 0, 6, 5\}$$$, the next artifact he steals must have a cost of at least $$$3$$$.

There is a special artifact initially at position $$$k$$$ in the row, and your goal is to prevent Thomas from stealing it. To do so, you may swap the positions of any pair of artifacts. Is it possible to stop Thomas from stealing the special artifact, and if so, which swap should you make?

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$1 \le k \le n$$$) — the number of artifacts and the initial position of the special artifact, respectively.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \cdots c_n$$$ ($$$0 \le c_i \le n$$$) — the costs of the artifacts, in order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, if it is impossible to stop Thomas from stealing the special artifact, print -1 -1.

Otherwise, print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) — the positions of the two artifacts to swap. You are allowed to choose a pair with $$$i = j$$$, in which case no swap will be made.

If there are multiple solutions, you may print any.

Example
Input
6
5 4
1 0 1 2 2
5 1
1 0 1 2 2
5 2
1 0 1 2 2
10 6
2 2 1 1 4 2 6 2 3 3
6 1
0 1 2 0 3 1
10 3
1 0 3 2 1 0 3 1 0 2
Output
3 5
1 4
-1 -1
-1 -1
1 5
8 3
Note

In the first test case, we swap artifacts $$$3$$$ and $$$5$$$, so this is what the row of artifacts will look like before and after the swap (with the special artifact in red):

$$$$$$[1, 0, 1, \color{red}{2}, 2] \rightarrow [1, 0, 2, \color{red}{2}, 1]$$$$$$

After the swap, Thomas will make the following moves, where $$$S$$$ is the set of costs of artifacts Thomas has stolen.

  • For the first artifact, $$$S = \{\}$$$, with a $$$\operatorname{MEX}$$$ of $$$0$$$. Since $$$c_1 = 1 \ge 0$$$, he steals the first artifact and adds $$$1$$$ to $$$S$$$.
  • For the second artifact, $$$S = \{1\}$$$, with a $$$\operatorname{MEX}$$$ of $$$0$$$. Since $$$c_2 = 0 \ge 0$$$, he steals the second artifact and adds $$$0$$$ to $$$S$$$.
  • For the third artifact, $$$S = \{0, 1\}$$$, with a $$$\operatorname{MEX}$$$ of $$$2$$$. Since $$$c_3 = 2 \ge 2$$$, he steals the third artifact and adds $$$2$$$ to $$$S$$$.
  • For the fourth artifact, $$$S = \{0, 1, 2\}$$$, with a $$$\operatorname{MEX}$$$ of $$$3$$$. Since $$$c_4 = 2 \lt 3$$$, he does not steal the fourth artifact.
  • For the fifth artifact, $$$S = \{0, 1, 2\}$$$, with a $$$\operatorname{MEX}$$$ of $$$3$$$. Since $$$c_5 = 1 \lt 3$$$, he does not steal the fifth artifact.

Since he doesn't steal the special artifact on position $$$4$$$, we have succeeded.

In the second test case, we swap artifacts $$$1$$$ and $$$4$$$, so the artifacts will look like this before and after the swap:

$$$$$$[\color{red}{1}, 0, 1, 2, 2] \rightarrow [2, 0, 1, \color{red}{1}, 2]$$$$$$

Note that the position of the special artifact has changed, so our goal is to stop Thomas from stealing the artifact in position $$$4$$$ after the swap. If we simulate the process as in the first test case, we can see that Thomas will not steal it.

In the third test case, we can show that no matter what swap we make, Thomas will always steal the artifact with cost $$$0$$$.

In the fourth test case, since there are no artifacts with cost $$$0$$$, the $$$\operatorname{MEX}$$$ of the costs of the stolen artifacts will always be $$$0$$$, and Thomas will steal every artifact, no matter what swap is made.