说明

对于一个有序的信号 $s_1, s_2, \ldots, s_n$，信号中的每个数都是正整数。当应用一个模糊滤镜在此信号上时，会得到新的信号 $t_1, t_2, \ldots, t_n$，新信号的值为 $t_1 = \lfloor (s_1+s_2)/2 \rfloor$，$t_2 = \lfloor (s_1+s_2+s_3)/3 \rfloor$，$t_3 = \lfloor (s_2+s_3+s_4)/3 \rfloor$，$\ldots$，$t_{n-1} = \lfloor (s_{n-2}+s_{n-1}+s_n)/3 \rfloor$，$t_n = \lfloor (s_{n-1}+s_n)/2 \rfloor$，其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

现在给出了模糊后的信号 $t$，请计算信号 $s$。如果有多个 $s$ 满足要求，请找到 $s_1$ 最小的一种，如果有多个 $s_1$ 相等的满足要求，请找出 $s_2$ 最小的一种，依次类推，请找出 $s_1, s_2, s_3, \ldots, s_n$ 最小的一种。

输入格式

输出的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，依次为 $t_1, t_2, \ldots, t_n$。

输出格式

输出一行，包含 $n$ 个整数，依次表示 $s_1, s_2, \ldots, s_n$。注意，$s$ 中的每个数都应是正整数。

5
1 2 3 4 5

1 1 4 4 6

提示

【数据规模和约定】

对于 $40\%$ 的评测用例，$2 \le n \le 20$，信号 $t$ 中每个数为不超过 $100$ 的正整数；

对于 $60\%$ 的评测用例，$2 \le n \le 300$，信号 $t$ 中每个数为不超过 $100$ 的正整数；

对于所有评测用例，$2 \le n \le 5000$，信号 $t$ 中每个数为不超过 $1000000$ 的正整数。

请注意，以上都是信号 $t$ 中每个数的范围，信号 $s$ 中每个数可能会超过此范围。