The key observation here is how many combinations a given output has. Consider the sample output grouped by type: 2 9 9 9. The counts of the elements look like this:

2 : 1
9 : 3

Now for each element, recall that two sets with the same amount of all elements are the same. Assuming the rest of our elements have ~K~ combinations, and our last element has ~3~ total, we have ~4K~ total sets. Why? We can choose to have any number from ~0, 1, 2, 3~ of our last element, and no matter which we choose, we have ~K~ combinations for the rest of our elements, for a total of ~4K~ combinations.

Let us have ~M~ distinct elements, each with counts ~C_i~. Then the total number of combinations is:

$$\displaystyle \prod_{i = 1}^M (C_i + 1) - 1$$

We subtract the empty combination here.

As an example suppose we are given ~K = 7~, as in the sample input. Then we need:

$$\displaystyle \prod_{i = 1}^M (C_i + 1) - 1 = 7$$ $$\displaystyle \prod_{i = 1}^M (C_i + 1) = 8$$

Well, since we get to choose ~M~, what if we just factor ~8~?

And indeed, the sample input has ~C = \{1, 3\}~. Another valid output for ~K = 7~ is 1 2 3, which has ~C = \{1, 1, 1\}~.

This should give us the understanding to solve the first subtask. We can simply output ~K~ of the same integer, since ~K~ is so small.

For the remaining subtasks, we note that we can find the sum of ~C~ to be minimal in order to check if it fits under the constraint ~N \le 10^5~. In other words, we must find a set of numbers ~C_i~ such that

$$\displaystyle \prod_{i = 1}^M (C_i + 1) = K + 1$$

and

$$\displaystyle \sum_{i = 1}^M C_i$$

is minimum. By making a change of variable of ~C_i + 1 = D_i~, it follows that

$$\displaystyle \prod_{i = 1}^M D_i = K + 1$$

and we are trying to minimize

$$\displaystyle \sum_{i = 1}^M D_i - 1$$

Now consider that there exists a ~D_i~ such that there exist positive integers ~a, b~ where ~ab = D_i~. We can try to immediately minimize the sum by replacing ~D_i~ with ~a~ and ~b~. In other words, we will replace ~D_i~ with ~a~ and ~b~ when

$$\displaystyle \begin{align*} ab - 1 &> a - 1 + b - 1 \\ ab - a - b + 1 &> 0 \\ (a - 1)(b - 1) &> 0 \\ \end{align*}$$

The only positive integer solutions to the inequality are when ~a, b \ge 2~, so it is always better to replace ~D_i~ with ~a~ and ~b~. Thus, the optimal solution should have all of ~D_i~ not factorable into ~a, b \ge 2~ meaning that all ~D_i~ should be prime. So, after factoring ~K~ into its prime factors, we can compare the sum against ~10^5~.

The second subtask rewards contestants who made these observations but implemented an inefficient solution, potentially by factoring in linear time.

The final subtask can be solved by factoring in ~\mathcal O(\sqrt{K})~ time or other efficient methods. Implementation details are left as an exercise to the reader.

Time Complexity: ~\mathcal O(\sqrt{K})~