提示: 欢迎访问OurACM平台。因与高数考试冲突,校赛改为5月6日13:00-17:00
Problem 1080 奇怪的数列

Accept: 198    Submit: 337
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

有一个长度为n (1<n<=100) 的数列,其中一些元素是正整数,其余元素是0。这些正整数会同时加倍,并将加倍后的数二等分后向左右两侧的元素转移,从而从一个状态转入其后继状态,如下图的一个状态:

0 6 0 8 0
经一次加倍转移后,其后继状态为:
6 0 14 0 8
特别要注意的是:第一个元素的数加倍后,向左边移动的数又回到原处。最后一个元素的数加倍后,向右边移动的数消失。如上述状态再经一次加倍转移后的后继状态是:
6 20 0 22 0
有些状态不可能是另一些状态的后继状态,我们称这样状态为“根状态”。给出一个状态,求它的根状态。

Input

第一行仅包含一个表示测试例个数的正整数n。以下 2n 行为测试例的输入数据。
每个测试例输入两行,第一行是一个正整数,为数列的长度。第二行为给定的一个数列,两数之间用一个空格隔开。

Output

每个测试例输出一行,包含数列的根状态下的各个元素,两数之间用一个空格隔开。

Sample Input

2 5 5 10 1 9 0 8 1 0 1 1 0 3 9 1

Sample Output

0 0 1 0 0 1 0 1 1 0 3 9 1

Source

FJNU Preliminary 2005

Submit  Back  Status  Discuss