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

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.