CF1468H.K and Medians

Let's denote the median of a sequence $s$ with odd length as the value in the middle of $s$ if we sort $s$ in non-decreasing order. For example, let $s = [1, 2, 5, 7, 2, 3, 12]$. After sorting, we get sequence $[1, 2, 2, \underline{3}, 5, 7, 12]$, and the median is equal to $3$.

You have a sequence of $n$ integers $[1, 2, \dots, n]$ and an odd integer $k$.

In one step, you choose any $k$ elements from the sequence and erase all chosen elements except their median. These elements do not have to go continuously (gaps are allowed between them).

For example, if you have a sequence $[1, 2, 3, 4, 5, 6, 7]$ (i.e. $n=7$) and $k = 3$, then the following options for the first step are possible:

• choose $[1, \underline{2}, 3]$; $2$ is their median, so it is not erased, and the resulting sequence is $[2, 4, 5, 6, 7]$;
• choose $[2, \underline{4}, 6]$; $4$ is their median, so it is not erased, and the resulting sequence is $[1, 3, 4, 5, 7]$;
• choose $[1, \underline{6}, 7]$; $6$ is their median, so it is not erased, and the resulting sequence is $[2, 3, 4, 5, 6]$;
• and several others.

You can do zero or more steps. Can you get a sequence $b_1$, $b_2$, ..., $b_m$ after several steps?

You'll be given $t$ test cases. Solve each test case independently.

我们用中位数表示一个长度为奇数的序列 $s$ 的中间值，即当 $s$ 按非递减顺序排序后位于正中间位置的元素。例如，设 $s = [1, 2, 5, 7, 2, 3, 12]$，排序后得到序列 $[1, 2, 2, \underline{3}, 5, 7, 12]$，其中位数为 $3$。

你有一个由 $n$ 个整数组成的序列 $[1, 2, \dots, n]$，以及一个奇数 $k$。

每一步操作中，你可以从当前序列中任意选出 $k$ 个元素，并仅保留它们的中位数，其余 $k-1$ 个被选中的元素均被删除（所选 $k$ 个元素在原序列中不必连续，允许存在间隔）。

例如，若当前序列为 $[1, 2, 3, 4, 5, 6, 7]$（即 $n=7$），且 $k = 3$，则第一步可能的操作包括：

• 选择 $[1, \underline{2}, 3]$；其中位数为 $2$，因此仅保留 $2$，其余两个被删去，结果序列为 $[2, 4, 5, 6, 7]$；
• 选择 $[2, \underline{4}, 6]$；其中位数为 $4$，因此仅保留 $4$，其余两个被删去，结果序列为 $[1, 3, 4, 5, 7]$；
• 选择 $[1, \underline{6}, 7]$；其中位数为 $6$，因此仅保留 $6$，其余两个被删去，结果序列为 $[2, 3, 4, 5, 6]$；
• 还有其他多种可能。

你可以执行零次或多次上述操作。问：能否通过若干次操作得到目标序列 $b_1$, $b_2$, ..., $b_m$？

你将收到 $t$ 组测试用例。请独立求解每组测试用例。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains three integers $n$, $k$, and $m$ ($3 \le n \le 2 \cdot 10^5$; $3 \le k \le n$; $k$ is odd; $1 \le m \lt n$) — the length of the sequence you have, the number of elements you choose in each step and the length of the sequence you'd like to get.

The second line of each test case contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_1 \lt b_2 \lt \dots \lt b_m \le n$) — the sequence you'd like to get, given in the ascending order.

It's guaranteed that the total sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$k$ 和 $m$（$3 \le n \le 2 \cdot 10^5$；$3 \le k \le n$；$k$ 为奇数；$1 \le m \lt n$）—— 分别表示你所拥有的序列长度、每步选取的元素个数，以及你希望得到的目标序列长度。

每个测试用例的第二行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \le b_1 \lt b_2 \lt \dots \lt b_m \le n$）—— 以升序给出的你希望得到的目标序列。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, print YES if you can obtain the sequence $b$ or NO otherwise. You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

对于每个测试用例，如果可以得到序列 $b$，则输出 YES；否则输出 NO。每个字母的大小写均可（例如，YES、Yes、yes、yEs 均被视为肯定回答）。

In the first test case, you have sequence $[1, 2, 3]$. Since $k = 3$ you have only one way to choose $k$ elements — it's to choose all elements $[1, \underline{2}, 3]$ with median $2$. That's why after erasing all chosen elements except its median you'll get sequence $[2]$. In other words, there is no way to get sequence $b = [1]$ as the result.

In the second test case, you have sequence $[1, 2, 3, 4, 5, 6, 7]$ and one of the optimal strategies is following:

1. choose $k = 3$ elements $[2, \underline{3}, 4]$ and erase them except its median; you'll get sequence $[1, 3, 5, 6, 7]$;
2. choose $3$ elements $[3, \underline{5}, 6]$ and erase them except its median; you'll get desired sequence $[1, 5, 7]$;

In the fourth test case, you have sequence $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]$. You can choose $k=7$ elements $[2, 4, 6, \underline{7}, 8, 10, 13]$ and erase them except its median to get sequence $b$.

在第一个测试用例中，你拥有序列 $[1, 2, 3]$。由于 $k = 3$，你仅有一种方式选择 $k$ 个元素——即选择全部元素 $[1, \underline{2}, 3]$，其中中位数为 $2$。因此，在擦除所选元素中除其中位数外的所有元素后，你将得到序列 $[2]$。换言之，无法通过该操作得到结果序列 $b = [1]$。

在第二个测试用例中，你拥有序列 $[1, 2, 3, 4, 5, 6, 7]$，其中一种最优策略如下：

1. 选择 $k = 3$ 个元素 $[2, \underline{3}, 4]$，并擦除其中除中位数外的所有元素；你将得到序列 $[1, 3, 5, 6, 7]$；
2. 选择 $3$ 个元素 $[3, \underline{5}, 6]$，并擦除其中除中位数外的所有元素；你将得到目标序列 $[1, 5, 7]$；

在第四个测试用例中，你拥有序列 $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]$。你可以选择 $k=7$ 个元素 $[2, 4, 6, \underline{7}, 8, 10, 13]$，并擦除其中除中位数外的所有元素，从而得到序列 $b$。