题目描述

• 文件输入：cool.in
• 文件输出：cool.out

给定一个大小为 $n$ 的数组 $a$，以及一个参数 $k$，如果满足以下条件，则称数组 $b$ 是 酷的：

• 对于每个从 $k$ 到 $n$ 的 $i$，数组 $[a_{i-k+1}, a_{i-k+2}, \ldots, a_i]$ 是 $[b_{i-k+1}, b_{i-k+2}, \ldots, b_i]$ 的一个重排列。

给定两个大小为 $n$ 的数组 $a$ 和 $b$，以及一个整数 $k$。数组 $a$ 仅包含从 $1$ 到 $n$ 的整数。数组 $b$ 仅包含从 $1$ 到 $n$ 的整数，以及 $-1$。

判断是否可以将 $b$ 中的所有 $-1$ 替换为 $1$ 到 $n$ 之间的整数，使得 $b$ 关于 $k$ 是 酷的。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

每个测试用例的第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出格式

对于每个测试用例，如果可能，输出 YES，否则输出 NO。

样例

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

YES
YES
YES
NO
NO

说明/提示

样例解释

在第一个测试用例中，$k=5$。唯一大小为 $5$ 的子数组是 $[1,5]$。我们可以看到 $b$ 是 $a$ 的一个重排列，所以答案是 YES。

在第二个测试用例中，我们可以令 $b=[2,1,2,1,2]$。我们可以看到 $a$ 和 $b$ 中每个大小为 $2$ 的窗口要么是 $[1,2]$ 要么是 $[2,1]$，它们互为重排列，所以答案是 YES。

在第四个测试用例中，因为 $a_1 \neq b_1$ 且 $k=1$，所以答案是 NO。

数据规模与约定

对于所有的数据：$1 \le t \le 10^4$，$1 \leq k \leq n \leq 2\cdot 10^5$，$1 \leq a_i \leq n$，$1 \leq b_i \leq n$ 或 $b_i=-1$，且 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于子任务 $i(i \gt 1)$，你需要答对所有编号 $\lt i$ 的子任务才能获得子任务 $i$ 的得分。

测试样例

一共 $5$ 组测试样例。

$cool\texttt{i}.in$ 和 $cool\texttt{i}.ans$ 对应子任务 $i$。

点击下载 测试样例