Chouti работает над странной математической задачей.
Была некоторая последовательность из \(n\) положительных целых чисел \(x_1, x_2, \ldots, x_n\), где число \(n\) чётное. Последовательность была очень особенной, а именно для каждого целого \(t\) от \(1\) до \(n\), \(x_1+x_2+...+x_t\) является квадратом некоторого целого числа (то есть полным квадратом).
Неведомым образом, числа с нечётными индексами пропали, то есть известны только числа с чётными индексами, другими словами \(x_2, x_4, x_6, \ldots, x_n\). Задача состоит в том, чтобы восстановить изначальную последовательность. Он снова просит у вас помощи с решением этой задачи.
Автор задачи может допускать ошибки, поэтому подходящая последовательность может и не существовать. Если же существует несколько подходящих последовательностей, выведите любую.
Выходные данные
Если не существует ни одной подходящей последовательности, выведите «No».
Иначе, выведите «Yes» и \(n\) положительных целых чисел \(x_1, x_2, \ldots, x_n\) (\(1 \le x_i \le 10^{13}\)) в следующей строке, при этом \(x_2, x_4, \ldots, x_n\) должны совпадать с числами во входных данных. Если существует несколько возможных ответов, выведите любой.
Заметьте, что ограничение на \(x_i\) больше, чем во входных данных. Можно доказать, что если ответ существует, то существует и последовательность, удовлетворяющая \(1 \le x_i \le 10^{13}\).
Примечание
В первом примере
- \(x_1=4\)
- \(x_1+x_2=9\)
- \(x_1+x_2+x_3=25\)
- \(x_1+x_2+x_3+x_4=36\)
- \(x_1+x_2+x_3+x_4+x_5=100\)
- \(x_1+x_2+x_3+x_4+x_5+x_6=144\)
Все эти числа являются полными квадратами.
Во втором примере, \(x_1=100\), \(x_1+x_2=10000\). Эти числа являются полными квадратами. Существуют и другие возможные ответы. Например, \(x_1=22500\) является другим возможным ответом.
В третьем примере можно показать, что подходящей последовательности не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 11 44
|
Yes
4 5 16 11 64 44
|
|
2
|
2
9900
|
Yes
100 9900
|
|
3
|
6
314 1592 6535
|
No
|