CF1787E.The Harmonization of XOR

You are given an array of exactly $n$ numbers $[1,2,3,\ldots,n]$ along with integers $k$ and $x$.

Partition the array in exactly $k$ non-empty disjoint subsequences such that the bitwise XOR of all numbers in each subsequence is $x$, and each number is in exactly one subsequence. Notice that there are no constraints on the length of each subsequence.

A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements.

For example, for $n = 15$, $k = 6$, $x = 7$, the following scheme is valid:

• $[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$,

where $\oplus$ represents the bitwise XOR operation.

The following scheme is invalid, since $8$, $15$ do not appear:

• $[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$.

The following scheme is invalid, since $3$ appears twice, and $1$, $2$ do not appear:

• $[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$.

你将得到一个恰好包含 $n$ 个数的数组 $[1,2,3,\ldots,n]$，以及整数 $k$ 和 $x$。

请将该数组恰好划分为 $k$ 个非空、互不相交的子序列，使得每个子序列中所有数的按位异或（XOR）结果均为 $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$。

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first and the only line of each test case contains three integers $n$, $k$, $x$ ($1 \le k \le n \le 2 \cdot 10^5$; $1\le x \le 10^9$) — the length of the array, the number of subsequences and the required XOR.

It's guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$）—— 分别表示数组长度、子序列数量以及目标异或值。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, if it is possible to partition the sequence, print "YES" in the first line. In the $i$-th of the following $k$ lines first print the length $s_i$ of the $i$-th subsequence, then print $s_i$ integers, representing the elements in the $i$-th subsequence. If there are multiple answers, print any. Note that you can print a subsequence in any order.

If it is not possible to partition the sequence, print "NO".

对于每个测试用例，如果可以将序列划分为若干子序列，则在第一行输出 "YES"。接下来的 $k$ 行中，第 $i$ 行首先输出第 $i$ 个子序列的长度 $s_i$，然后输出 $s_i$ 个整数，表示该子序列中的元素。若存在多种可行方案，输出任意一种即可。注意：每个子序列中的元素顺序可以任意。

如果无法划分该序列，则输出 "NO"。

In the first test case, we construct the following $6$ subsequences:

• $[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$.

In the second test case, we construct the following $4$ subsequences:

• $[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$.

The following solution is considered correct in this test case as well:

• $[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$.

在第一个测试用例中，我们构造了以下 $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$。