No.451 575

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 68
作問者 : 🐬hec🐬hec

5 ProblemId : 1416 / 出題時の順位表

Note

この問題はAdvent Calendar Contest Advent Calendar 2016の2日目の問題として作られました。

ストーリー(読まなくても解けます)

イルカは最近「本日はYukicoderの出題日」などと呟くと,他の動物たちに575を指摘されます.このため,575を検出することに興味を持っています.

ところで,問題の出題日は12月2日ですが,これに何か見覚えありませんか?
そうです.日付を{12,2}という数列にみなすと,12=5+7 2=7-5 より,{5,7,5}が出てきます.
つまり,{5,7,5}の{初項と第2項の和,第2項から第3項を引いた差}で[12,2]ができています.

この考え方を拡張すると,ある数列の左から連続する2つの項に注目して,和と差を交互に取り出すことにより新しい数列を生成できます.
この事実をイルカに教えたところ,上で生成された長さnの数列から元の長さn+1の数列に分解できるのに興味を持ちました.
そこで,そんなイルカのためにプログラムを書いて検証してあげることにしました.

問題文

$n$項の数列$\{b_1,b_2,\cdots,b_n\}$が与えられます.次の条件満たす$n+1$項の数列$\{a_1,a_2,\cdots,a_n,a_{n+1}\}$を出力してください.

$\begin{eqnarray} b_i = \begin{cases} a_i+a_{i+1} & (i \equiv 1 \mod 2) \\ a_i-a_{i+1} & (i \equiv 0 \mod 2) \end{cases}\end{eqnarray} (1 \le i \le n)$

$1 \le a_i \le 10^{18} \ (1 \le i \le n+1)$
$a_i \in \mathbb{N} \ (1 \le i \le n+1)$

入力

$n$
$b_1$
$b_2$
$\vdots$
$b_n$

$1 \le n \le 10^5$
$1 \le b_i \le {10}^{18} \ (1 \le i \le n)$
$b_i \in \mathbb{N} \ (1 \le i \le n)$

出力

条件を満たす数列$\{a_1,a_2,\cdots,a_n,a_{n+1}\}$がない場合には以下のように$-1$を出力してください.

$-1$
そうでなければ,以下の形式で条件を満たす数列を出力してください.
$n+1$
$a_1$
$a_2$
$\vdots$
$a_{n+1}$
最後に改行してください。

サンプル

サンプル1
入力
2
12
2
出力
3
5
7
5

ストーリーに書いてある部分の例です.

サンプル2
入力
1
5
出力
2
1
4

他にも{2,3},{3,2}などが条件を満たします.

サンプル3
入力
1
1
出力
-1

2つの正の整数の和は2以上になるため,条件を満たす数列は存在しません.

サンプル4
入力
10
933
925
304
138
179
19
101
13
469
200
出力
11
1
932
7
297
159
20
1
100
87
382
182

提出ページヘ