「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现)

J. 数青蛙

单点时限: 2.0 sec

内存限制: 256 MB

Helen 在做数青蛙的实验。按照「青蛙爷爷的秘诀」一书上介绍的:由于东方神秘力量的影响,青蛙的个数是一个完美的等比数列,例如:1, 2, 4, 8, 16…

她每天都去池塘记录青蛙的个数。但是记录出了偏差,Helen 有一天在数青蛙的时候开了个小差,数错了。于是这个等比数列就不完美了。不过作为一个聪明的小孩,Helen 可以把记录重新改对。

给出 Helen $n$ 天的实验记录,记录中有且仅有一个数是错误的。请修改这一个错误并输出正确的实验记录。

输入格式

输入包含多个测试文件,每个测试文件只有一个测试点。

第一行是一个整数 $n$ $(1 \leq n \leq 50)$,下面一行给出 $n$ 个整数:$a_1, a_2, \ldots, a_n$ $(0 \leq a_i \leq 10^{18})$。

对于约 40% 的测试点,满足:$1 \leq n \leq 3$。

输入保证有解。

输出格式

输出正确的实验记录:$n$ 个整数 $b_1, b_2, \ldots b_n$。输出应保证 $1 \leq b_i \leq 10^{18}$。

如果有多解,输出任意一解。

样例

Input
5
1 2 5 8 16
Output
1 2 4 8 16