GCD of Prefixes Problem Code: GCDPRF Answer

 » CodeChef Starters 17 Division 3 (Rated) » GCD of Prefixes

GCD of Prefixes

Problem Code: GCDPRF

Add problem to Todo list

Submit

Sasuke and Itachi are playing a game. Sasuke first creates an array A containing N positive integers A1,A2,…,AN. He then creates a new array B of length N such that Bi=gcd(A1,A2,...,Ai) for each 1≤i≤N. Now, Sasuke gives array B to Itachi and asks him to find any array A (with 1≤Ai≤109) such that the given process applied to A will produce B. Can you help Itachi solve this problem?

Here, gcd stands for greatest common divisor.

Input Format

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N.

The second line contains N space-separated integers B1,B2,…,BN

Output Format

For each test case, print a single line containing N space-separated integers denoting the array A you constructed. If no such array A exists, print −1 instead.

Constraints

1≤T≤103

1≤N≤105

1≤Ai,Bi≤109

It is guaranteed that sum of N over all test cases doesn't exceed 5×105.

Sample Input 1 

2

2

4 2

2

1 3

Sample Output 1 

4 26

-1

Explanation

Test Case 1: One possible answer is [4,26] because B can be generated as follows: B=[gcd(4),gcd(4,26)]=[4,2].

Test Case 2: It can be shown that no array A exists which can produce the given B.

Click Here For Answer