K-th Smallest Element in a BST

You are given a binary search tree (BST) represented by its level order traversal. Some nodes may be missing, represented by the token null. For each test case, you are also given an integer \(k\). Your task is to find the \(k\)-th smallest element in the BST. If the BST does not contain \(k\) elements, print \(-1\).

The BST is constructed using its level order traversal. Note that the given level order is guaranteed to represent a valid BST.

Example:

Input:
2
3 7
5 3 8 2 4 6 9
1 5
7 3 9 2 5

Output:
4
2

In the first test case, the BST formed from the level order [5, 3, 8, 2, 4, 6, 9] has the in-order traversal [2, 3, 4, 5, 6, 8, 9], so the 3rd smallest element is 4.

inputFormat

The first line contains an integer \(T\) representing the number of test cases.

For each test case, there are two lines:

• The first line contains two integers \(k\) and \(n\), where \(k\) is the position of the smallest element you need to find and \(n\) is the number of nodes in the level order traversal.
• The second line contains \(n\) tokens separated by spaces. Each token is either an integer or the string null (indicating a missing node).

Note: The tokens represent the level order traversal of a BST.

outputFormat

For each test case, output a single integer on a new line: the \(k\)-th smallest element in the BST. If the BST contains fewer than \(k\) nodes, output \(-1\).

## sample

5
3 7
5 3 8 2 4 6 9
1 5
7 3 9 2 5
5 7
4 2 6 1 3 5 7
10 7
50 30 70 20 40 60 80
1 1
10

4
2
5
-1
10

</p>