#2359. 铅笔与盒子

铅笔与盒子

题目描述

给出 n\red{n}个铅笔,每个铅笔都有某个颜色 ,a1a2,...,an\red{a_1a_2,...,a_n,}现在需要把笔放入盒子里,使其满足以下条件:

每个铅笔都必须恰好分入一个盒子中 每一个盒子中必须至少包含 k\red{k}个铅笔 在每一盒子中,铅笔的颜色之差的绝对值不能超过d.\red{d .}

即当铅笔 i,j\red{i,j}在同一个盒子中时,需要满足 aiaj<=d\red{|a_i-a_j|<=d}

注意:相反的,如果 aiaj<=d\red{|a_i-a_j|<=d} ,i,j\red{i,j}也可以属于不同盒子

请判断是否存在满足条件的分组方案,若有请输出"YES\red{YES}",否则输出"NO\red{NO}"(不带引号)。

输入格式

第一行一个整数T\red{T ,}数据组数。 接下来每组测试数据中,第一行三个整数 n,k,d\red{n,k,d,}铅笔数量,每个盒子中的最少铅笔数,同一盒子的铅笔的最大绝对值差。 第二行有 n\red{n}个整数,表示铅笔的颜色。

输出格式

每组数据输出"YES\red{YES}"或"NO\red{NO}"。

样例

输入样例1

2

6 3 10 

7 2 7 7 4 2 

6 2 3 

4 5 3 13 4 10

输出样例1

YES 

YES

输入样例2

1

3 2 5 

10 16 22

输出样例2

NO

提示

对于50%\red{50\%}的数据满足

1<=k<=n<=1000\red{1<=k<=n<=1000}

对于100%\red{100\%}的数据满足

1<=k<=n<=5×\red{1<=k<=n<=5×}105,1,=ai,d<=109,1<=T<=15\red{10^5,1,=a_i,d<=10^9,1<=T<=15}