Mock Canadian Computing Competition: 2026 Senior #4

Swing is the brand new mobile game that challenges people to swing across platforms. The prize? Currency! Everyone knows that the best mobile games always come with micro-transactions. However, as the free-to-play player he is, he loves to maximize his rewards.

This time, Moonlight has won big! His winnings are ~M~ pieces of currency, in possible denominations worth ~1, \frac{1}{2}, \frac{1}{3}, ..., \frac{1}{500000}~ moon dollars. However, it's never that easy to collect all of that prize money: Moonlight can only use at most ~N~ bags to fit his winnings, each of which can contain at most a total value of ~1~ moon dollar. For example, a bag could fit a piece worth ~\frac{1}{2}~ a moon dollar and another piece worth ~\frac{1}{3}~ a moon dollar for a sum of ~\frac{5}{6}~ moon dollars.

However, he knows that the ~M~ pieces of currency can be distributed into these bags since he sees there is at most a total of ~N-\frac{1}{2}~ moon dollars lying on the ground (which he mathematically proved)! After spending all this time proving this fact, he's exhausted and wants your help to determine any valid way to distribute his earnings into the bags for him.

Input Specification

The first line will contain two space-separated integers ~N, M~, representing the number of bags Moonlight has, and the number of pieces of currency lying on the ground, respectively.

The second line will contain ~M~ space-separated integers ~x_i~, representing the ~M~ pieces of currency he sees, where each piece is worth ~\frac{1}{x_i}~.

The following table shows how the available 15 marks are distributed. Subtasks do not have to be completed in order and you do not need to solve the sample cases to be graded for each subtask.

Marks	Bounds on ~N~ and ~M~	Bounds on ~x_i~	Additional Constraints
~4~ marks	~1 \le N \leq M \leq 500~	~1 \le x_i \le 500\,000~	None
~3~ marks	~1 \le N \le M \leq 100\,000~	~1 \le x_i \le 500\,000~	Each ~x_i~ is guaranteed to be a power of ~2~
~8~ marks	~1 \le N \le M \le 500\,000~	~1 \le x_i \le 500\,000~	None

Note that Moonlight knows that ~\sum{\frac{1}{x_i}} \leq N-\frac{1}{2}~, and it is always possible to come up with a valid construction.

Output Specification

The first line of output must contain an integer ~1 \leq Q \leq N~, representing the number of bags being used to collect the currency. Note that the value of ~Q~ does not have to be optimal.

The next ~Q~ lines of output must begin with a positive integer ~K~, representing the number of pieces of currency in the bag. On the same line, there should be ~K~ space separated integers ~x_i~, denoting the pieces of currency in the bag.

For each case, if any bag does not satisfy ~\sum{\frac{1}{x_i}} \leq 1~, or not all the currency is collected, or there is extra currency being collected not specified by the problem input, you will receive a WA verdict. Otherwise, you will receive an AC verdict.

Keep in mind that the judge is very strict. Ensure that you have no trailing whitespace in your output and each line must end with a newline character '\n'.

For example, the lines '3 10 10 10\n' and '3 10 10 10 \n' and '3 10 10 10' are very different; only the first is acceptable.

Sample Input 1

3 3
1 4 2

Possible Output for Sample Input 1

3
1 1
1 2
1 4

Explanation of Output for Sample Input 1

Moonlight can use all ~N=3~ bags, each containing a singular currency, with each totalling a value of ~1, \frac{1}{2}, \frac{1}{4}~ moon dollars, respectively. Note that this is not the only valid option, and you do not need to use all ~N~ bags. Keep in mind that

3
1 1
0
2 2 4

is not valid.

Sample Input 2

3 7
5 4 7 4 1 10 3

Possible Output for Sample Input 2

3
1 1
3 5 7 10
3 4 3 4

Explanation of Output for Sample Input 2

The first bag has ~1~ moon dollar, the second bag has ~\frac{31}{70}~ moon dollars, and the third bag has ~\frac{5}{6}~ moon dollars.