B. Покраска
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Cirno_9baka есть бумажная лента с $$$n$$$ клетками, расположенными в ряд. Поскольку он считает, что чистая бумажная лента слишком скучна, он хочет раскрасить клетки в $$$m$$$ цветов. Из эстетических соображений он считает, что $$$i$$$-й цвет должен быть использован ровно $$$a_i$$$ раз, а также, что для каждых $$$k$$$ последовательных клеток их цвета должны быть попарно различными.

Помогите Cirno_9baka выяснить, существует ли такой способ раскрасить клетки.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$)  — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq k \leq n \leq 10^9$$$, $$$1 \leq m \leq 10^5$$$, $$$m \leq n$$$). Здесь $$$n$$$ обозначает количество клеток, $$$m$$$  — количество цветов, а $$$k$$$ означает, что для каждых $$$k$$$ последовательных клеток, их цвета должны быть попарно различными.

Вторая строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$a_1, a_2, \cdots , a_m$$$ ($$$1 \leq a_i \leq n$$$)  — обозначающие, сколько раз цвета должны быть использованы. Гарантируется, что $$$a_1 + a_2 + \ldots + a_m = n$$$.

Гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превышает $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если существует хотя бы одна возможная схема раскраски; в противном случае выведите «NO».

Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «Yes» и «YEs» будут распознаны как положительные ответы).

Пример
Входные данные
2
12 6 2
1 1 1 1 1 7
12 6 2
2 2 2 2 2 2
Выходные данные
NO
YES
Примечание

В первом наборе входных данных нет способа раскрасить клетки, удовлетворяющего всем условиям.

Во втором наборе входных данных мы можем раскрасить клетки следующим образом: $$$(1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6)$$$. Для любых $$$2$$$ последовательных клеток, их цвета различны.