P4934 Gift

Because you did an excellent job on the previous two problems, the kind __stdcall decided to give you a small gift, providing strong support for you who are striving to AK this problem set.

__stdcall decided to give you $n$ gifts. Each gift has a magic value $a_i$. All magic values are unique, i.e., pairwise distinct. These gifts have magical power: if for two gifts $i, j$, their magic values satisfy $a_i \operatorname{bitand} a_j \ge \min(a_i, a_j)$, then their magic will cancel each other out, so they cannot be put into the same box. Here $\operatorname{bitand}$ denotes the bitwise AND operation. If you are not familiar with it, please refer to: . As the gift delivery worker, ljt12138 does not have many boxes, but luckily each box is large enough. Now he asks you to help him distribute the gifts properly, using **as few** boxes as possible. In other words, make sure every gift is placed into exactly one box, and the gifts in the same box will not cancel each other out. If there are multiple valid solutions, you only need to output **any one**. ljt12138 is very kind: if you can only compute the required number of boxes, you can still get $60\%$ of the score for that test point. For details, see the hints and explanations below.

- The first line contains two numbers $n$ and $k$, where $n$ is the total number of gifts, and $k$ is a parameter to help you compute. - The second line contains $n$ pairwise distinct numbers $a_i$, satisfying $0 \le a_i < 2^k$, representing the magic values of the gifts.

- Output one number on the first line. If you do not want to output an assignment, output $0$; if you want to output an assignment, output $1$. **If you output invalid information on this line, you will be judged as WA**. - Output one number $m$ on the second line, indicating that you packed the gifts into $m$ boxes. - If you output $1$ on the first line, then output the next $m$ lines, each describing one box: first a number $s_i$, the number of gifts in the current box; then $s_i$ numbers describing the current subset.

### Additional Samples You can download additional samples at . ### About Outputting an Assignment - If you output $0$ on the first line and correctly answer the minimum number of boxes needed, you will get $60\%$ of the score for that test point. - If you output $1$ on the first line, correctly answer the minimum number of boxes needed, but do not provide a correct assignment, you will also get $60\%$ of the score for that test point. - If you do not correctly answer the minimum number of boxes needed, you will not get the score for that test point. - Please note that if you do not output in the format above, you will not receive any score. The relationship between $n$ and $k$ is given by the table below: |Data ID| $n$ | $k$ | |:----:|:----:|:----:| |$1$|$5$|$3$| |$2$|$6$|$3$| |$3$|$7$|$10$| |$4$|$8$|$10$| |$5$|$16$|$7$| |$6$|$17$|$8$| |$7$|$17$|$9$| |$8$|$17$|$20$| |$9$|$2\times 10^3$|$17$| |$10$|$2.5\times 10^3$|$18$| |$11$|$3\times 10^3$|$19$| |$12$|$3\times 10^3$|$20$| |$13$|$2.5\times 10^4$|$15$| |$14$|$2.5\times 10^4$|$15$| |$15$|$5\times 10^4$|$16$| |$16$|$5\times 10^4$|$16$| |$17$|$2.5\times 10^5$|$18$| |$18$|$5\times 10^5$|$19$| |$19$|$10^6$|$20$| |$20$|$10^6$|$20$| Translated by ChatGPT 5