Find the k-th Smallest Element in a BST

You are given T test cases. For each test case, you are provided with an integer N representing the number of elements, an integer K representing the position of the k-th smallest element to find, and a list of N integers. Insert the integers one by one into a binary search tree (BST) using the following rule: if the value to be inserted is less than or equal to the current node’s value, insert it into the left subtree; otherwise, insert it into the right subtree.

After constructing the BST, perform an in-order traversal to obtain the elements in sorted order. Your task is to output the k-th smallest element of the BST for each test case.

The in-order traversal of a BST provides the sorted order of its elements. In mathematical terms, if the in-order sequence is \(a_1, a_2, \dots, a_n\), then the answer is \(a_k\), where \(1 \leq k \leq n\).

inputFormat

The first line contains an integer T, the number of test cases. Then for each test case:

• A line containing two integers N and K, where N is the number of elements and K is the position of the k-th smallest element.
• A line containing N space-separated integers.

Input should be read from stdin.

outputFormat

For each test case, output a single line containing the k-th smallest element of the BST. Output should be printed to stdout.

## sample

2
5 3
5 3 8 2 4
7 4
10 5 1 7 40 50 8

4
8

</p>