B. Find The Array

B. Find The Array

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array [a1,a2,…,an][a1,a2,…,an] such that 1≤ai≤1091≤ai≤109. Let SS be the sum of all elements of the array aa.

Let's call an array bb of nn integers beautiful if:

• 1≤bi≤1091≤bi≤109 for each ii from 11 to nn;
• for every pair of adjacent integers from the array (bi,bi+1)(bi,bi+1), either bibi divides bi+1bi+1, or bi+1bi+1 divides bibi (or both);
• 2∑i=1n|ai−bi|≤S2∑i=1n|ai−bi|≤S.

Your task is to find any beautiful array. It can be shown that at least one beautiful array always exists.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

Each test case consists of two lines. The first line contains one integer nn (2≤n≤502≤n≤50).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

Output

For each test case, print the beautiful array b1,b2,…,bnb1,b2,…,bn (1≤bi≤1091≤bi≤109) on a separate line. It can be shown that at least one beautiful array exists under these circumstances. If there are multiple answers, print any of them.

Example

input

Copy

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

output

Copy

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

=========================================================================

很巧妙，突破点在于 不等式左边的2，不妨让bi一定小于ai,这样的话，我们将bi构造成第一个小于ai的2的若干次幂。这样二者只差一定小于ai/2

证明如下，如果 bi*2==ai 那么恰好是一半

bi*2>ai 那么一定小于一半

bi*2

#include 
#include 
#include 
#include 
#include 
#include 
 
using namespace std;
typedef long long ll;
 
ll er[50];
void init()
{
    er[0]=1ll;
 
    for(int i=1;i<=32;i++)
    {
        er[i]=er[i-1]*2ll;
    }
}
int main()
{
 
     int t;
     init();
     cin>>t;
 
     while(t--)
     {
         int n,x;
 
         cin>>n;
 
         for(int i=1;i<=n;i++)
         {
            cin>>x;
            cout<max(0ll,lower_bound(er,er+33,x)-er-1)]<<" ";
         }
         cout<
     }
 
    return 0;
}