The Wormhole Queue

There are several Wormholes across the galaxy that are used to travel by the galactic civilization.They allow usage of wormhole only one at a time to prevent temporal timeline issues. Each wormhole has a well known travel cost. The Space Council maintains a list of costs:and ships always try to take the cheapest available wormhole at that time. After processing a series of wormhole discoveries and departures, Space Council analysts need to know the Kth smallest travel cost still available so they can guide the spaceships appropriately. Additionally they also want to query how far are they from the current median(defined below) of costs for planning purposes.
Your goal is to help them to get to this info as fast as possible.

Your Task

Given a list of ~N~ integers and an integer ~K~, output the ~Kth~ smallest value (1-indexed) in the array. Additionally output the median (middle value if ~N~ is odd, lower-middle if ~N~ is even) of the sorted array.

Input Specification

• Line 1: ~T~ — number of queries.
• Each query:
  • Line 1: two integers ~N~ and ~K~
  • Line 2: ~N~ space-separated integers

Output Specification

For each query print two space-separated values: the ~Kth~ smallest and the median.

Sample Input

2
5 2
3 1 4 1 5
6 4
9 3 7 1 5 2

Sample Output

1 3
5 4

Constraints

~1 \le T \le 100\,000~
~1 \le K \le N \le 100\,000~
~-10^9 \le values \le 10^9~

Test cases available here!