6.3 Push and Pop

Score: 60pts

Time Limit: 3.00 sec

You have a stack of N integers.With a single magic spell you can either pop an element from the stack or push any popped element into the stack.

You need to maximize the top element of the stack after performing exactly K spells. If the stack becomes empty after performing K spells and there is no other way for the stack to be non-empty, print -1.

Make sure that you handle all the edge cases.

You need to maximize the top element of the stack after performing exactly K spells. If the stack becomes empty after performing K spells and there is no other way for the stack to be non-empty, print -1.

Make sure that you handle all the edge cases.

Constraints

1 <= N <= 1e6

1 <= Ai <= 10^18

1 <= K <= 10^9

1 <= Ai <= 10^18

1 <= K <= 10^9

Input Format

The first line contains the number of test cases t .

The next 2t lines of input consists of two space-separated integers N and K.

The next line of input consists N space-separated integers denoting the elements of the stack. The first element represents the top of the stack and the last element represents the bottom of the stack.

The next 2t lines of input consists of two space-separated integers N and K.

The next line of input consists N space-separated integers denoting the elements of the stack. The first element represents the top of the stack and the last element represents the bottom of the stack.

Output Format

Print the maximum possible top element of the stack after performing exactly K spells.

Example 1

Input:

3

6 4

1 2 4 3 3 5

4 2

3 4 5 6

1 4

5

Output:

4

5

5

Explanation:

In the first test cases we remove the first three elements using the spell 3 times and in the last spell we push 4 back into it making the top as maximum.

In the second test case we see that after popping 2 elements the elements present on the top is already greater.

In the third test case we can pop , push , pop , push the same element so the it eventually becomes the max.

3

6 4

1 2 4 3 3 5

4 2

3 4 5 6

1 4

5

Output:

4

5

5

Explanation:

In the first test cases we remove the first three elements using the spell 3 times and in the last spell we push 4 back into it making the top as maximum.

In the second test case we see that after popping 2 elements the elements present on the top is already greater.

In the third test case we can pop , push , pop , push the same element so the it eventually becomes the max.