Statement : C2. Equal Multisets (Hard Version)

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$.

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$.

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

Input

5
5 5
1 2 3 4 5
3 1 5 2 4
5 2
1 2 1 2 1
2 -1 -1 -1 -1
6 1
5 6 2 2 4 3
5 -1 -1 2 -1 3
2 1
1 2
2 -1
6 4
1 2 3 4 1 2
2 -1 3 -1 4 -1

Output

YES
YES
YES
NO
NO

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.