Correct Gp :
Difficulty Level : Hard
Submissions : 103
Asked In :
Marks :100
: 1 | : 1
Rohan hates maths and his teacher gives him a question related to Geometric Progression (GP). He was given an array of GP sequences which is $$$a_i$$$, $$$a_{i+1}$$$ ..... $$$a_{n-1}$$$ but his teacher wants that Rohan to come up with the correct GP sequence. The only operation he is allowed to do is insert some elements $$$a_i$$$ for which the Gp ratio between every two consecutive elements became equally. If no solution exists print -1. Also, his teacher asked him to maximise the ratio of GP.
Now Rohan needs your help to find the correct GP sequence which has a maximum ratio
The first line of the test case contains a single integer N ($$$0 \le N \le 10^5$$$) — the length of sequence that teaches gave to Rohan.
The second line of each test case contains N integers $$$a_i$$$, $$$a_{i+1}$$$ ..... $$$a_{n-1}$$$ ($$$0 \le a_i \le 2*10^4$$$) — the sorted incorrect GP .
For each test case print the correct sequence of the array if it exists else print -1.
3 64 100 125
64 80 100 125
4 2 8 16 32
2 4 8 16 32
