Рассмотрим массив \(a_1, a_2, \dots, a_n\) состоящий из чисел \(1\) и \(-1\). Назовем его \(A\)-характеристикой количество пар индексов \(1 \le i < j \le n\) таких, что \(a_i \cdot a_j = 1\).
Вам необходимо найти любой массив \(a\) заданной длины \(n\), \(A\)-характеристика которого равна заданному \(k\).
Выходные данные
Для каждого набора входных данных, если нет массива \(a\) с \(A\)-характеристикой равной \(k\), выведите NO.
Иначе выведите YES и \(n\) чисел \(1\) и \(-1\), которые формируют требуемый массив \(a\). Если есть несколько решений, выведите любой из них.
Примечание
В первом наборе есть лишь одна пара различных элементов в массиве, и их произведение \(a_1 \cdot a_2 = -1 \neq 1\), поэтому его \(A\)-характеристика равна \(0\).
Во втором наборе есть лишь одна пара различных элементов в массиве, и их произведение \(a_1 \cdot a_2 = 1\), поэтому его \(A\)-характеристика равна \(1\).
Во третьем наборе есть три пары различных элементов в массиве, и их произведение \(a_1 \cdot a_2 = -1\), \(a_1 \cdot a_3 = 1\), \(a_2 \cdot a_3 = -1\), поэтому его \(A\)-характеристика равна \(1\).
В четвертом наборе можно показать что не существует массива длины \(3\), \(A\)-характеристика которого равна \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2 0
2 1
3 1
3 2
3 3
5 4
5 5
|
YES
1 -1
YES
1 1
YES
1 -1 1
NO
YES
1 1 1
YES
-1 1 -1 1 1
NO
|