Alice loves to play with array of integers. He has an array A[ ] of integers. Bob, friend of Alice is a smart guy. Seeing Alice’s curiousness about array Bob decided to give Alice a task. Before giving the task Bob ask Alice if he knows about K_min_subarray? A K_min_subarray is the minimum value of a K length subarray of array A[ ]. After Bob knows about K_min_subarray, Alice gives Bob Q queries about array A[ ]. In each query she will give two integers L, R. Alice have to answer the largest value of all possible K_min_subarray in between L to R. Here each subarray’s starting position must be >= L, ending position must be <= R and the length of the subarray must be K.

Input

In the first line given t, the number of test cases.

For each test case there will be the following:

In the first line given two integers n (Size of the array) and K (Length of the subarray).

In the second line given the elements (A[i]) of the array.

In the next line given an integer Q (the number of queries).

In the next Q lines are given two integers L, R

Constraints

1 <= t <= 10

1 <= n <= 10^5

1 <= K <= n

-10^18 <= A[i] <= 10^18

1 <= Q <= 10^5

1 <= L <= R <= n

t * max(n, Q) <= 10^5

Output

For each test case you have to print the test case number in one line in the format “Case x:” without quote, where x is the case number.

For each query output the largest value of all possible K_min_subarray in between L to R in each line. If answer is not possible print “Impossible” without quote.

For better understanding see the sample input output and the explanation of sample.

Example

Input:
2
7 3
10 5 15 -5 3 11 2
4
1 4
2 3
3 6
5 7
5 1
1 2 3 4 5
3
1 3
2 5
4 4

Output:
Case 1:
5
Impossible
-5
2
Case 2:
3
5
4

Explanation

Test Case 1:

Query 1: Here 2 subarray possible of length 3 between positions 1 to 4: {10, 5, 15}, {5, 15, -5}.

Minimum value in {10, 5, 15} is 5 Minimum value in {5, 15, -5} is -5 Maximum of 5 and -5 is 5.

So answer is 5.

Query 2: Here no subarray is possible of length 3 between positions 2 to 3.

So you have to print “Impossible”.

Query 3: Here 2 subarray possible of length 3 between positions 3 and 6: {15, -5, 3}, {-5, 3, 11}.

Minimum value in {15, -5, 3} is -5 Minimum value in {-5, 3, 11} is -5 Maximum of -5 and -5 is -5.

So the answer is -5.

This problem originally contributed by Md. Mozahidul Islam (kissu_pari_na), ICT, CoU