406773: GYM102536 L Break the Pattern!

Tasked with finding new recruits for the Division of Cryptographic Secrets, you put up a place where you can observe people's talents in finding clues, solving puzzles, and uncovering mysteries: an Escape the Room game!

You've thought of something that can be used to unlock one of the doors in the Room. To get feedback, you've approached your friends Andy, Natalie, and Dylan.

You ask them, "Complete the pattern: 1, 2, 3, 5, X. What is X?"

Andy quickly answers, "8! Isn't it just the Fibonacci sequence?"

Almost immediately, Natalie says, "Could also just be the roots of $$$x^5 - 19x^4 + 129x^3 -389x^2 + 518x - 240$$$."

Dylan then adds, "Isn't it a bit ambiguous? Technically you could have any piecewise function. How about adding some constraints?"

You take their feedback into account. After contemplating for a bit, you propose a variant. "Alright, how about this. Given the sequence, output $$$n$$$ distinct nonzero polynomials that 'fit' the sequence, with maximum degree $$$k$$$."

This variant seems fair enough to them. "Time to test the puzzle then," they say. Andy, Natalie, and Dylan take turns in giving you random sequences, while you need to reply with the different polynomials that could fit those sequences. Here, "fitting" means that the polynomial will evaluate to zero for all of the integers in the given sequence.

The first line of input starts with an integer $$$t$$$, the number of sequences.

$$$t$$$ sequences follow, described in two lines each.

The first line for each sequence consists of three integers $$$n$$$, $$$k$$$, and $$$\ell$$$, each separated by a space. $$$n$$$ and $$$k$$$ are as described previously, while $$$\ell$$$ denotes the length of the sequence.

The second line for each sequence contains the $$$\ell$$$ integers $$$s_1, s_2, \ldots, s_\ell$$$ that make up the sequence, separated by single spaces.

Constraints

• $$$1 \le t \le 2500$$$
• $$$1 \le n, k, \ell \le 50$$$
• $$$-400000 \le s_i \le 400000$$$

For each of the $$$t$$$ sequences, output the following:

If less than $$$n$$$ such polynomials exist, print how many there are on its own line, followed by those polynomials. If there are at least $$$n$$$, print $$$n$$$ on its own line, followed by any $$$n$$$ polynomials.

Output each polynomial on each own line. First output its degree $$$d$$$, followed by exactly $$$d+1$$$ space-separated integer coefficients in decreasing order of exponents. The leading coefficient must not be zero.

The absolute value of the coefficients must also be less than or equal to $$$10^9$$$.

Important: For this problem, we treat the integers as congruent modulo $$$999983$$$. In other words, two integers $$$x$$$ and $$$y$$$ are considered equal if $$$999983$$$ divides $$$x - y$$$. (This implies that two polynomials $$$p$$$ and $$$q$$$ are considered equal if every coefficient of $$$p - q$$$ is divisible by $$$999983$$$. For example, $$$x - 1$$$ is considered the same as $$$999984x + 999982$$$, etc.)

There may be multiple valid answers. Any valid answer will be accepted.

3
1 5 4
1 2 3 5
1 3 4
1 2 3 5
1 4 3
3 7 42

1
5 1 -19 129 -389 518 -240
0
1
4 1 -52 441 -882 0

Note that 5 1 999964 129 -389 518 999743 is also a valid output for the first test case and is equivalent to the sample output above. (For example, evaluating it at $$$1$$$ will give $$$1999966$$$ which is equivalent to $$$0$$$ since $$$1999966 - 0$$$ is divisible by $$$999983$$$, so $$$1$$$ is a root.)