E. Распределение XOR
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив из ровно $$$n$$$ чисел $$$[1,2,3,\ldots,n]$$$, а также целые числа $$$k$$$ и $$$x$$$.

Вам нужно разбить массив на ровно $$$k$$$ непустых непересекающихся подпоследовательностей так, чтобы побитовое исключающее ИЛИ всех чисел в каждой подпоследовательности было равно $$$x$$$, и каждое число находилось ровно в одной подпоследовательности. Обратите внимание, что нет никаких ограничений на длину каждой подпоследовательности.

Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов.

Например, для $$$n = 15$$$, $$$k = 6$$$, $$$x = 7$$$ корректно следующее разбиение:

  • $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,
  • $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,
  • $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,
  • $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,
  • $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,
  • $$$[7]$$$, $$$7 = 7$$$,
где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Следующее разбиение некорректно, так как не используются числа $$$8$$$ и $$$15$$$:

  • $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,
  • $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,
  • $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,
  • $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,
  • $$$[7]$$$, $$$7 = 7$$$.

Следующее разбиение некорректно, так как $$$3$$$ встречается дважды, а $$$1$$$, $$$2$$$ не используются:

  • $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,
  • $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,
  • $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,
  • $$$[3,4]$$$, $$$3 \oplus 4 = 7$$$,
  • $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,
  • $$$[7]$$$, $$$7 = 7$$$.
Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$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».

Пример
Входные данные
7
15 6 7
11 4 5
5 3 2
4 1 4
6 1 7
11 5 5
11 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$$$ подпоследовательностей:

  • $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,
  • $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,
  • $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,
  • $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,
  • $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,
  • $$$[7]$$$, $$$7 = 7$$$.

Во втором наборе входных данных мы строим следующие $$$4$$$ подпоследовательности:

  • $$$[1,4]$$$, $$$1 \oplus 4 = 5$$$,
  • $$$[2,7]$$$, $$$2 \oplus 7 = 5$$$,
  • $$$[3,6]$$$, $$$3 \oplus 6 = 5$$$,
  • $$$[5,8,9,10,11]$$$, $$$5 \oplus 8 \oplus 9 \oplus 10 \oplus 11 = 5$$$.

Следующей разбиение также будет считаться правильным в этом наборе входных данных:

  • $$$[1,4]$$$, $$$1 \oplus 4 = 5$$$,
  • $$$[2,7]$$$, $$$2 \oplus 7 = 5$$$,
  • $$$[5]$$$, $$$5 = 5$$$,
  • $$$[3,6,8,9,10,11]$$$, $$$3 \oplus 6 \oplus 8 \oplus 9 \oplus 10 \oplus 11 = 5$$$.