F. Too Many BSTs
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You're given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$,and an array of $$$q$$$ integers $$$x_1, x_2, \ldots, x_q$$$. It is guaranteed that all integers $$$a_1, a_2, \ldots, a_n, x_1, x_2, \ldots, x_q$$$ are distinct.

You need to answer $$$q$$$ queries. For the $$$i$$$-th query, find the height$$$^\dagger$$$ of the BST(binary search tree) constructed by inserting $$$n + 1$$$ elements in the order of $$$x_i, a_1, a_2, \ldots, a_n$$$.

Formally, for the $$$i$$$-th query, we set the BST $$$T$$$ empty initially. Then, we run the function $$$\texttt{insert}(T, x_i), \texttt{insert}(T, a_1), \texttt{insert}(T, a_2), \ldots , \texttt{insert}(T, a_n)$$$ in order.

function insert(T, x)
    if T is null:
        newNode = Node(x) // Create a new node with value x
        T = newNode       // Set newNode as the root of the tree
    else if x < T.value:
        T.left = insert(T.left, x)   // Recursively insert x into the left subtree
    else if x > T.value:
        T.right = insert(T.right, x) // Recursively insert x into the right subtree
    return T                         // Return the root of the modified tree

$$$^\dagger$$$The height of a tree refers to the length of the longest path from the root node to any leaf node in the tree. It represents the number of edges on the longest downward path between the root node and a leaf.

Input

The first line contains an integer $$$t(1 \leq t \leq 10^5)$$$, the number of test cases.

For each test case:

  • The first line contains two integers $$$n$$$ and $$$q$$$$$$(2 \leq n,q \leq 5 \cdot 10^5)$$$, the number of elements in the array and the number of queries, respectively.
  • The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$, representing the elements of the array.
  • The third $$$q$$$ line contains $$$q$$$ space-separated integers $$$x_1, x_2, \ldots, x_q$$$ $$$(1 \leq x_i \leq 10^9)$$$, representing the queries.
  • It is guaranteed that all integers $$$a_1, a_2, \ldots, a_n, x_1, x_2, \ldots, x_q$$$ are distinct.

It is guaranteed the sum of $$$n$$$ and the sum of $$$q$$$ will not exceed $$$5 \cdot 10^5$$$ over all test cases respectively.

Output

For each query, output in a new line  — $$$q$$$ space-separated integers, the answer of the $$$q$$$ queries.

Example
Input
2
3 2
1 4 3
2 5
5 6
5 9 2 999999999 20
16 1 6 4 10 1000000000
Output
2 3
2 4 3 4 2 4
Note

In the first test case, the final BST for the $$$1$$$-st and $$$2$$$-nd queries are shown as follows.

The final BST for the $$$1$$$-st query. The height of this BST is $$$2$$$.
The final BST for the $$$2$$$-nd query. The height of this BST is $$$3$$$.