构造数组(Find The Array)

题目描述

给定一个数组 $a=[a_1,\dots,a_n]\ (1\le a_i\le 10^9)$。设 $S$ 为 $a$ 所有元素之和。称一个长度为 $n$ 的整数数组 $b$ 为"美丽数组"若满足：

• $1\le b_i\le 10^9$（$i=1\dots n$）；
• 对每一对相邻元素 $(b_i, b_{i+1})$，要么 $b_i$ 整除 $b_{i+1}$，要么 $b_{i+1}$ 整除 $b_i$（或两者）；
• $2\cdot\sum_{i=1}^{n}|a_i-b_i| \le S$。 你需要找出任意一个美丽数组。可以保证至少存在一个。

输入格式

第一行一个整数 $t\ (1\le t\le 1000)$ — 测试组数。 每组两行：第一行一个整数 $n\ (2\le n\le 50)$；第二行 $n$ 个整数 $a_1\dots a_n\ (1\le a_i\le 10^9)$。

输出格式

每组输出一行美丽数组 $b_1\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

数据范围

$1\le t\le 1000$；$2\le n\le 50$；$1\le a_i\le 10^9$。

知识点与难度

本题涉及的知识点从属于 GESP 五级，难度等级：⭐⭐

测试点分布