← 返回题目列表

Codeforces · 1463/B

B. 查找数组

中文机器翻译题面 查看原题

给定一个数组 $$$[a_1, a_2, \dots, a_n]$$$,使得 $$$1 \le a_i \le 10^9$$$。令$$$S$$$ 为数组$$$a$$$ 中所有元素的总和。

如果满足以下条件,我们称 $$$n$$$ 整数的数组 $$$b$$$ 为漂亮:

- $$$1 \le b_i \le 10^9$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$;
- 对于数组$$$(b_i, b_{i + 1})$$$中的每对相邻整数,要么$$$b_i$$$除$$$b_{i + 1}$$$,要么$$$b_{i + 1}$$$除$$$b_i$$$(或两者);
- $$$2 \sum \limits_{i = 1}^{n} |a_i - b_i| \le S$$$。

你的任务是找到任何漂亮的数组。可以证明,至少有一个美丽的数组总是存在的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

输出

对于每个测试用例,在单独的行上打印漂亮的数组 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$)。可以证明,在这种情况下,至少存在一种美丽的阵法。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
5
1 2 3 4 5
2
4 6
2
1 1000000000
6
3 4 8 1 2 3

输出 #1

3 3 3 3 3
3 6
1 1000000000
4 4 8 1 3 3