This is the hard version of the problem. The difference between the versions is that in this version, the array $$$a$$$ is arbitrary. You can hack only if you solved all versions of this problem.

Given an array $$$a$$$ of size $$$n$$$, and a parameter $$$k$$$, an array $$$b$$$ is called cool if the following conditions hold:

For each $$$i$$$ from $$$k$$$ to $$$n$$$, the array $$$[a_{i-k+1},a_{i-k+2},\ldots,a_i]$$$ is a rearrangement of $$$[b_{i-k+1},b_{i-k+2},\ldots,b_i]$$$.

You are given two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$, and an integer $$$k$$$. The array $$$a$$$ only contains integers from $$$1$$$ to $$$n$$$. The array $$$b$$$ only contains integers from $$$1$$$ to $$$n$$$, and $$$-1$$$.

Determine if it is possible to replace all $$$-1$$$ in $$$b$$$ with an integer from $$$1$$$ to $$$n$$$, such that $$$b$$$ is cool with respect to $$$k$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$).

The third line of each test case contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq n$$$ or $$$b_i=-1$$$).

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output YES if possible, and NO otherwise. You may print each letter in either uppercase or lowercase.

Note

In the first test case, we have $$$k=5$$$. The only subarray of size $$$5$$$ is $$$[1,5]$$$. We can see that $$$b$$$ is a rearrangement of $$$a$$$, so the answer is YES.

In the second test case, we can have $$$b=[2,1,2,1,2]$$$. We can see that each window of size $$$2$$$ in both $$$a$$$ and $$$b$$$ are either $$$[1,2]$$$ or $$$[2,1]$$$, which are rearrangements of each other, so the answer is YES.

In the fourth test case, since $$$a_1 \neq b_1$$$ and $$$k=1$$$, the answer is NO.

Equal Multisets (Hard Version)

Examples