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 he 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 (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 given two integers L , R

 

Constrains:

    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

 

Here all positions are 1 based.

Output

For each test case you have to output the following-

Print the test case no 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 pos 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 & -5 is 5.

                            So, answer is 5

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

                             So, you have to print “Impossible”  

                    Query 3: Here 2 subarray possible of length 3 between pos 3 & 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 & -5 is -5.

                             So, answer is -5.

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