Недавно Феде на день рождения подарили массив \(a\) из \(n\) целых чисел, записаных по кругу, в котором для каждой пары соседних элементов (\(a_1\) и \(a_2\), \(a_2\) и \(a_3\), \(\ldots\), \(a_{n - 1}\) и \(a_n\), \(a_n\) и \(a_1\)) модуль их разности равен \(1\).
Назовём локальным максимумом элемент, который больше обоих соседних элементов. Также назовём локальным минимумом элемент, который меньше обоих соседних элементов. Обратите внимание, что элементы \(a_1\) и \(a_n\) являются соседними.
К сожалению, Федя потерял массив, но он запомнил в нём сумму локальных максимумов \(x\) и сумму локальных минимумов \(y\).
По заданным \(x\) и \(y\) помогите Феде найти любой подходящий массив минимальной длины.
Выходные данные
Для каждого набора входных данных в первой строке выведите одно число \(n\) — минимальную длину подходящего массива.
Во второй строке выведите \(n\) чисел \(a_1, a_2, \ldots, a_n\) (\(-10^{9} \leqslant a_i \leqslant 10^{9}\)) — элементы массива, такие что модуль разности каждой пары соседних равен \(1\).
Если существуют несколько решений, выведите любое из них.
Гарантируется, что сумма значений \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^{5}\).
Примечание
В первом наборе входных данных локальными максимумами являются числа на позициях \(3, 7\) и \(10\), а локальными минимумами числа на позициях \(1, 6\) и \(8\). \(x = a_3 + a_7 + a_{10} = 2 + 0 + 1 = 3\), \(y = a_1 + a_6 + a_8 = 0 + (-1) + (-1) = -2\).
Во втором наборе входных данных локальными максимумами являются числа на позициях \(2\) и \(10\), а локальными минимумами числа на позициях \(1\) и \(3\). \(x = a_2 + a_{10} = -1 + 5 = 4\), \(y = a_1 + a_3 = -2 + (-2) = -4\).
В третьем наборе входных данных локальными максимумами являются числа на позициях \(1\) и \(5\), а локальными минимумами числа на позициях \(3\) и \(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 -2
4 -4
2 -1
5 -3
|
10
0 1 2 1 0 -1 0 -1 0 1
16
-2 -1 -2 -1 0 1 2 3 4 5 4 3 2 1 0 -1
6
1 0 -1 0 1 0
16
2 3 2 1 0 -1 0 -1 0 -1 0 1 2 1 0 1
|