Так и не став гроссмейстером за два месяца, Николай окончательно разочаровался в карьере в спортивном программировании и решил податься в политический стриминг.
Как известно, ни один стример не может существовать без поддержки своих любимых зрителей, поэтому каждый стрим Николаю в обязательном порядке приходит некоторое число донатов, образующих последовательность $$$a$$$. Обратите внимание, что Николая смотрит большое количество хакеров, из-за чего некоторые донаты могут иметь отрицательный размер.
Николай считает донат под номером $$$m$$$ весьма приятным, если его размер не меньше среднего значения всех предыдущих отправленных донатов, то есть для него выполняется $$$a_m \cdot (m - 1) \ge \sum\limits_{i=1}^{m-1} a_i$$$. В частности, первый отправленный донат всегда является весьма приятным.
Николай считает проведенный стрим окупившимся, если за время трансляции ему пришло ровно $$$k$$$ весьма приятных донатов.
Николай знает, что сегодня он получит $$$n$$$ донатов от зрителей, однако он не знает, в каком порядке. Пожалуйста, помогите зрителям выбрать порядок отправки донатов таким образом, чтобы порадовать Николая и окупить стрим!
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — количество донатов и необходимое число весьма приятных донатов.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — размеры донатов.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «NO», если подходящего порядка отправки донатов не существует.
Иначе в первой строке выведите «YES», а во второй строке — $$$n$$$ целых чисел: размеры донатов в порядке их отправки. Если существует несколько решений, выведите любое из них.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
43 11 2 33 15 5 53 2-1 -2 -34 30 0 10 -10
YES 3 2 1 NO YES -1 -3 -2 YES 10 -10 0 0
В первом наборе входных данных подходит порядок $$$[3, 2, 1]$$$. Первый донат всегда является весьма приятным. Второй не является весьма приятным, так как $$$2 \cdot 1 \lt 3$$$, а третий — так как $$$1 \cdot 2 \lt 3 + 2$$$. Таким образом, ровно $$$1$$$ донат является весьма приятным.
Во втором наборе входных данных можно показать, что подходящего порядка не существует.
В третьем наборе входных данных подходит порядок $$$[-1, -3, -2]$$$. Первый донат является весьма приятным. Второй не является весьма приятным, так как $$$(-3) \cdot 1 \lt -1$$$, а третий является, так как $$$(-2) \cdot 2 \ge -1 + (-3)$$$. Таким образом, ровно $$$2$$$ доната являются весьма приятными.
| Codeforces Round 1132 (Div. 2) |
|---|
| Закончено |
