Description

（特邀命题：2019届毕业生李昊霖）

某公司有 $N$ 名员工，公司整体工位为环形分布首尾相接摆放，工位按顺时针编号依次为 $1 \dots N$ 号。相邻员工间有一个张桌子，第$i$号桌子位于员工$i$和$i+1$之间（第$N$号桌子位于员工$N$和员工$1$之间），也就是共计有$N$张空桌子

每当员工 $i$ 收到 $x$ 份文件（题目保证$x$为偶数），他会将文件平均分到相邻两桌子上，也就是 $i-1$ 号空位和 $i$ 号空位分别堆放 $x/2$份文件。（$1$号员工会放到$N$号空位和$1$号空位上）

现在给出 员工数量 $N$ 和第 $i$ 个空位堆积的文件数 $a_i$ ,请你出计算每位员工收到的文件数。

Format

Input

第一行一个正整数 $N(3 \leqslant N \leqslant 10^{5}-1)$，保证 $N$ 是奇数。

第二行$N$个正整数 $a_i(0 \leqslant a_i \leqslant 10^{9})$

Output

$N$ 个整数，代表每位员工收到的文件数。

Samples

3
2 2 4

4 0 4

5
3 8 7 5 5

2 4 12 2 8

3
1000000000 1000000000 0

0 2000000000 0