MOVEBOOK - Move the books

no tags 

Sheldon and Lenard are a pair of nerds playing an unimaginatively named game, "Move the books". The game board is an infinitely long strip of cells numbered 1,2,3.... from left to right. On certain cells, their favourite physics books have been placed. A player's move consists of taking any one of the books and moving it to any cell which lies to its left. But there is a constraint that you are not allowed to make your book jump over a cell that contains a book already (ie, You cannot move a book from cell j to cell i < j if there is a cell k which contains one or more books such that i < k < j). However, you can place a book into a cell even if it contains one or more books already. But books that are placed in a cell are stacked in the order in which they arrive and hence only the topmost book (the last arrived one) can be moved from there. The players make moves alternately, and the person unable to move any book loses.

They have been playing the game for a long time. Sheldon makes the first move in all the games and wins most of the time. Lenard is fed up and wants to make the first move. However, Sheldon doesn't yield and this leads to an argument. This is the final agreement they have come up with:

  • They start with N books placed in different cells. The arrangement is computer generated and hence there is no player role in this step
  • Lenard picks two natural numbers a & c while Sheldon picks a natural number b. Both are unaware of the number(s) the other person has chosen while choosing their own number(s). Three more books are now added to the set : a cells to the right of the rightmost current book, b cells to the right of this book and c cells to the right of the latter book.
  • They start the game with the same rules as earlier, with Sheldon making the first move.

 

Now Lenard feels that there might be certain pairs (a,c) such that independent of which number Sheldon chooses, Lenard is assured to win the game. Given the initial configuration of the board find all such pairs, sort them lexicographically [(a1,c1) < (a2,c2) iff a1 < a2 or (a1=a2 and c1 < c2)] and output the Kth such pair. If there are less than K pairs with this property, output Impossible

Input

The first line of the Input contains T (≤50), the number of test cases. Following this are the descriptions of the T test cases

The first line in the description of each test case contains two space separated integers N (≤1000) and K (≤108). Following these are N lines, each containing the location of a book. The book positions are given in increasing order and will each fit in a 32 bit signed integer.

Output

For each test case output the Kth lexicographically smallest pair of integers that will assure Lenard a win. The two integers should be separated by a space and pairs for each test case should be output on a new line. If for any test case there are less than K pairs of integers that assure Lenard a win, on the line for that test case output Impossible

Example

Input:
1
1 1
1

Output:
1 1


Added by:Raziman T V
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IOPC2011