题目描述

Farmer John has fallen behind on organizing his inbox. The way his screen is organized, there is a vertical list of folders on the left side of the screen and a vertical list of emails on the right side of the screen. There are $M$ total folders, numbered $1 \ldots M$ $(1 \le M \le 10^4)$. His inbox currently contains $N$ emails numbered $1\ldots N$ $(1 \le N \le 10^5)$; the $i$th email needs to be filed into folder $f_i$ $(1\le f_i\le M)$.

FJ's screen is rather small, so he can only view $K$ $(1\le K\le \min(N,M))$ folders and $K$ emails at once. Initially, his screen starts out displaying folders $1 \ldots K$ on the left and emails $1 \ldots K$ on the right. To access other folders and emails, he needs to scroll through these respective lists. For example, if he scrolls down one position in the list of folders, his screen will display folders $2 \ldots K+1$, and then scrolling down one position further it will display folders $3 \ldots K+2$. When FJ drags an email into a folder, the email disappears from the email list, and the emails after the one that disappeared shift up by one position. For example, if emails $1, 2, 3, 4, 5$ are currently displayed and FJ drags email 3 into its appropriate folder, the email list will now show emails $1, 2, 4, 5, 6$. FJ can only drag an email into the folder to which it needs to be filled.

Unfortunately, the scroll wheel on FJ's mouse is broken, and he can only scroll downwards, not upwards. The only way he can achieve some semblance of upward scrolling is if he is viewing the last set of $K$ emails in his email list, and he files one of these. In this case, the email list will again show the last $K$ emails that haven't yet been filed, effectively scrolling the top email up by one. If there are fewer than $K$ emails remaining, then all of them will be displayed.

Please help FJ determine if it is possible to file all of his emails.

输入格式

The first line of input contains $T$ $(1≤T≤10)$, the number of subcases in this input, all of which must be solved correctly to solve the input case. The $T$ subcases then follow. For each subcase, the first line of input contains $M,N$ and $K$. The next line contains $f_1\cdots f_N$.

It is guaranteed that the sum of $M$ over all subcases does not exceed $10^4$, and that the sum of $N$ over all subcases does not exceed $10^5$.

输出格式

Output $T$ lines, each one either containing either YES or NO, specifying whether FJ can successfully file all his emails in each of the $T$ subcases.

题目大意

题目描述

$Farmer John$ 在整理收件箱方面已经落后了。他的屏幕排列方式是，屏幕左侧有一个垂直的文件夹列表，屏幕右侧有一个垂直的电子邮件列表。共有 $M$ 个文件夹，编号为 $1 \dotsm M (1 \le M \le 10^4)$ 。他的收件箱当前包含 $N$ 封编号为 $1 \dotsm N (1 \le N \le 10^5)$ 的电子邮件；第 $i$ 封电子邮件需要归档到文件夹 $f_i (1 \le f_i \le M)$。

$FJ$ 的屏幕有些小，所以他同时只能查看 $K(1 \le M \le min(n,m))$个文件夹和 $K$ 封电子邮件。最初，他的屏幕左侧显示文件夹 $1 \dotsm K$，右侧显示电子邮件 $1 \dotsm K$。要访问其他文件夹和电子邮件，他需要滚动相应的列表。例如，如果他将文件夹列表向下滚动一个位置，他的屏幕将显示文件夹 $2 \dotsm K+1$，然后再向下滚动一个位置将显示文件夹 $3 \dotsm K+2$。当 $FJ$ 将一封电子邮件拖曳至一个文件夹时，该电子邮件将从电子邮件列表中消失，并且消失的电子邮件之后的电子邮件会向上移动一个位置。例如，如果当前显示的是电子邮件 $1,2,3,4,5$，然后 $FJ$ 将电子邮件 $3$ 拖曳至其对应的文件夹中，则电子邮件列表现在将显示电子邮件 $1,2,4,5,6$。$FJ$ 只可以将电子邮件拖曳至其需要归档的文件夹中。

不幸的是，$FJ$ 的鼠标滚轮坏了，所以他只能向下滚动，不能向上滚动。他可以实现类似向上滚动的唯一情况是，他正在查看他的电子邮件列表中的最后 $K$ 封电子邮件，并且他归档了其中的一封。在这种情况下，电子邮件列表将再继续显示尚未归档的最后 $K$ 封电子邮件，实际上使得最上方的电子邮件向上滚动了一个位置。如果剩余少于 $K$ 封电子邮件，则将显示所有电子邮件。

请帮助 $FJ$ 判断是否可能归档他的所有电子邮件。

输入格式

输入的第一行包含 $T (1 \le T \le 10)$，为当前测试用例中的子测试用例数量，所有子测试用例必须全部正确才能通过当前测试用例。以下是 $T$ 个子测试用例。每一个子测试用例的第一行包含 $M$，$N$ 和 $K$。第二行包含 $f_1…f_N$。

输入保证所有子测试用例的 $M$ 之和不超过 $10^4$，所有子测试用例的 $N$ 之和不超过 $10^5$。

输出格式

输出 $T$ 行，每行包含 "YES" 或 "NO"，表示对于 $T$ 个子测试用例中的每一个，$FJ$ 是否可以成功归档他的所有电子邮件。

数据范围

• 测试点 2-10 中，所有子测试用例的 $M$ 之和不超过 $10^3$。
• 测试点 11-12 没有额外限制。

6
5 5 1
1 2 3 4 5
5 5 1
1 2 3 5 4
5 5 1
1 2 4 5 3
5 5 2
1 2 4 5 3
3 10 2
1 3 2 1 3 2 1 3 2 1
3 10 1
1 3 2 1 3 2 1 3 2 1

YES
YES
NO
YES
YES
NO

提示

【数据范围】

• In inputs 2-10, the sum of $M$ over all subcases does not exceed $10^3$.
• In inputs 11-12, no additional constraints.