Феникс любит красивые массивы. Он считает массив красивым, если все его подмассивы длины \(k\) имеют равную сумму. Подмассив массива — это последовательность подряд идущих элементов массива.
У Феникса есть массив \(a\) длины \(n\). Он хочет вставить несколько (возможно, ноль) целых чисел в свой массив, чтобы он стал красивым. Вставляемые числа должны иметь значения от \(1\) по \(n\) включительно. Числа можно вставлять куда угодно (даже перед первым или после последнего элемента). Феникс не пытается минимизировать количество вставленных чисел.
Выходные данные
Для каждого набора входных данных, если невозможно получить крассивый массив, выведите -1. Иначе, выведите две строки.
В первой строке выведите длину красивого массива \(m\) (\(n \le m \le 10^4\)). Вам не нужно минимизировать \(m\).
Во второй строке выведите \(m\) целых чисел через пробел (\(1 \le b_i \le n\)) — красивый массив, который Феникс сможет получить вставляя несколько (возможно, ноль) целых чисел в свой массив \(a\). Вы можете выводить числа, которых не было в массиве \(a\) первоначально.
Если существует несколько решений, выведите любое. Гарантируется, что если мы можем сделать массив \(a\) красивым, то мы всегда сможем добиться этого при итоговой длине не более \(10^4\).
Примечание
В первом наборе входных данных, мы можем сделать массив \(a\) красивым, если вставим число \(1\) в позицию \(3\) (между двумя числами \(2\)). Теперь все подмассивы длины \(k=2\) будут иметь одинаковую сумму \(3\). Существует много других возможных решений, например:
- \(2, 1, 2, 1, 2, 1\)
- \(1, 2, 1, 2, 1, 2\)
Во втором наборе, массив уже красивый: все подмассивы длины \(k=3\) имеют одинаковую сумму \(5\).
В третьем наборе, можно показать, что невозможно вставить числа так, чтобы сделать массив \(a\) красивым.
В четвертом наборе, предложенный массив \(b\) является красивым — все его подмассивы длины \(k=4\) имеют равную сумму \(10\). Также существуют и другие решения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 2
1 2 2 1
4 3
1 2 2 1
3 2
1 2 3
4 4
4 3 4 2
|
5
1 2 1 2 1
4
1 2 2 1
-1
7
4 3 2 1 4 3 2
|