The multinomial expansion for the power of ~2~ is the key to solving this problem. The expansion of the square of the sum of elements ~X_1, X_2, \dots, X_n~ in the list ~X~ looks like:

$$\displaystyle \begin{align} \text{square of sum} &= (X_1 + X_2 + X_3 + \dots + X_N)^2 \\ &= X_1^2 + X_2^2 + X_3^2 + \dots + X_N^2 + 2 \cdot X_1 \cdot X_2 + 2 \cdot X_2 \cdot X_3 + 2 \cdot X_1 \cdot X_3 + \dots + 2 \cdot X_{N-1} \cdot X_N \\ &= \text{sum of squares} + 2 \cdot \text{sum of pairwise products} \end{align}$$

Let ~S(X)~ be the sum of elements, ~SQ(X)~ be the sum of squares of elements, and ~SP(X)~ be the sum of all pairwise products of elements of the list ~X~. We can now rewrite the above equation as:

$$\displaystyle S(X)^2 = SQ(X) + 2 \cdot SP(X)$$

We can also observe the following about how the above values change when an additional element ~n~ is added to the list ~X~:

$$\displaystyle \begin{align} S(X + [n]) &= S(X) + n \\ SQ(X + [n]) &= SQ(X) + n^2 \\ SP(X + [n]) &= SP(X) + n \cdot S(X) \end{align}$$

Our task is to achieve ~S(E')^2 = SQ(E')~, where ~E'~ is the extended list that we get by adding extra elements to ~E~. In other words, we want to make ~SP(E') = 0~.

Test Set 1: ~K = 1~

If we are allowed only a single addition, we must choose an element ~n~ such that ~SP(E + [n]) = 0~.

$$\displaystyle \begin{align} SP(E + [n]) = 0 \\ \implies SP(E) + n \cdot S(E) = 0 \\ \implies n \cdot S(E) = -SP(E) \end{align}$$

If ~S(E) \ne 0~, we can get a squary list whenever ~-SP(E) / S(E)~ is an integer, which happens if and only if ~S(E)~ divides ~SP(E)~. In that case, ~-SP(E) / S(E)~ is our answer.

If ~S(E) = 0~, then ~S(E + [n]) = n~. Since we want ~S(E + [n])^2 = SQ(E + [n])~, we need ~SQ(E + [n]) = n^2~. This is possible only if ~SQ(E) = 0~, that is, if all elements in ~E~ are zeros. In this case, we can choose any value as our answer. But if any element in ~E~ is not zero, it is impossible to get a squary list with only one addition.

Test Set 2: ~K > 1~

At first, the search space might seem hopelessly broad here. But we can observe (or surmise and then confirm) that it is always possible to get a squary list by adding only two elements:

• ~n_1 = 1 - S(E)~
• ~n_2 = -SP(E + [n_1])~

After adding ~n_1~, we have

$$\displaystyle S(E + [n_1]) = 1$$

After adding ~n_2~, we have

$$\displaystyle \begin{align} SP(E + [n_1, n_2]) &= SP(E + [n_1]) + n_2 \cdot S(E + [n_1]) \\ &= SP(E + [n_1]) + (-SP(E + [n_1])) \cdot 1 \\ &= 0 \end{align}$$

Thus, the two numbers satisfy the condition ~SP(E') = 0~. We can also see that since the numbers in the original list are each of magnitude no greater than ~10^3~, ~|n_1| \le 10^6 + 1~, and ~|n_2| \le 2 \cdot 10^{12}~, both well within the limits.