Вам дан массив из ровно $$$n$$$ чисел $$$[1,2,3,\ldots,n]$$$, а также целые числа $$$k$$$ и $$$x$$$.
Вам нужно разбить массив на ровно $$$k$$$ непустых непересекающихся подпоследовательностей так, чтобы побитовое исключающее ИЛИ всех чисел в каждой подпоследовательности было равно $$$x$$$, и каждое число находилось ровно в одной подпоследовательности. Обратите внимание, что нет никаких ограничений на длину каждой подпоследовательности.
Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов.
Например, для $$$n = 15$$$, $$$k = 6$$$, $$$x = 7$$$ корректно следующее разбиение:
Следующее разбиение некорректно, так как не используются числа $$$8$$$ и $$$15$$$:
Следующее разбиение некорректно, так как $$$3$$$ встречается дважды, а $$$1$$$, $$$2$$$ не используются:
Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая и единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$, $$$x$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$; $$$1\le x \le 10^9$$$) — длина массива, количество подпоследовательностей и требуемое значение XOR.
Гарантируется, что сумма $$$n$$$ не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных, если ответ существует, выведите «YES» в первой строке. В $$$i$$$-й из следующих $$$k$$$ строк сначала выведите целое число $$$s_i$$$ — длину $$$i$$$-й подпоследовательности, затем выведите $$$s_i$$$ целых чисел — саму $$$i$$$-ю подпоследовательность. Если ответов несколько, выведите любой. Обратите внимание, что вы можете вывести элементы подпоследовательности в любом порядке.
В противном случае выведите «NO».
715 6 711 4 55 3 24 1 46 1 711 5 511 6 5
YES 3 6 10 11 3 5 12 14 3 3 9 13 3 1 2 4 2 8 15 1 7 YES 2 1 4 2 2 7 2 3 6 5 5 8 9 10 11 NO YES 4 1 2 3 4 YES 6 1 2 3 4 5 6 NO NO
В первом наборе входных данных мы строим следующие $$$6$$$ подпоследовательностей:
Во втором наборе входных данных мы строим следующие $$$4$$$ подпоследовательности:
Следующей разбиение также будет считаться правильным в этом наборе входных данных:
Название |
---|