Phoenix and Beauty
Contest: Codeforces Round 638 (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, data structures, greedy, sortings

Phoenix loves beautiful arrays. An array is beautiful if all its subarrays of length $$$k$$$ have the same sum. A subarray of an array is any sequence of consecutive elements.

Phoenix currently has an array $$$a$$$ of length $$$n$$$. He wants to insert some number of integers, possibly zero, into his array such that it becomes beautiful. The inserted integers must be between $$$1$$$ and $$$n$$$ inclusive. Integers may be inserted anywhere (even before the first or after the last element), and he is not trying to minimize the number of inserted integers.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$).

The second line of each test case contains $$$n$$$ space-separated integers ($$$1 \le a_i \le n$$$) — the array that Phoenix currently has. This array may or may not be already beautiful.

Output format:
For each test case, if it is impossible to create a beautiful array, print -1. Otherwise, print two lines.

The first line should contain the length of the beautiful array $$$m$$$ ($$$n \le m \le 10^4$$$). You don't need to minimize $$$m$$$.

The second line should contain $$$m$$$ space-separated integers ($$$1 \le b_i \le n$$$) — a beautiful array that Phoenix can obtain after inserting some, possibly zero, integers into his array $$$a$$$. You may print integers that weren't originally in array $$$a$$$.

If there are multiple solutions, print any. It's guaranteed that if we can make array $$$a$$$ beautiful, we can always make it with resulting length no more than $$$10^4$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can make array $$$a$$$ beautiful by inserting the integer $$$1$$$ at index $$$3$$$ (in between the two existing $$$2$$$s). Now, all subarrays of length $$$k=2$$$ have the same sum $$$3$$$. There exists many other possible solutions, for example:

- $$$2, 1, 2, 1, 2, 1$$$
- $$$1, 2, 1, 2, 1, 2$$$

In the second test case, the array is already beautiful: all subarrays of length $$$k=3$$$ have the same sum $$$5$$$.

In the third test case, it can be shown that we cannot insert numbers to make array $$$a$$$ beautiful.

In the fourth test case, the array $$$b$$$ shown is beautiful and all subarrays of length $$$k=4$$$ have the same sum $$$10$$$. There exist other solutions also.

Example input:
4
4 2
1 2 2 1
4 3
1 2 2 1
3 2
1 2 3
4 4
4 3 4 2

Example output:
5
1 2 1 2 1
4
1 2 2 1
-1
7
4 3 2 1 4 3 2

Editorial:
For an array to be beautiful for some $$$k$$$, the array must be periodic with period $$$k$$$. If there exists more than $$$k$$$ distinct numbers in the array $$$a$$$, there is no answer and we print -1 (because the array cannot be periodic with period $$$k$$$). Otherwise, we propose the following construction.
Consider a list of all the distinct numbers in array $$$a$$$. If there are less than $$$k$$$ of them, we will append some $$$1$$$s (or any other number) until the list has size $$$k$$$. We can just print this list $$$n$$$ times. The length of our array $$$b$$$ is $$$nk$$$, which never exceeds $$$10^4$$$. Array $$$b$$$ can always be constructed by inserting some numbers into array $$$a$$$ because every number in $$$a$$$ corresponds to one list.
Time complexity for each test case: $$$O(n \log{n}+nk)$$$