Produse2

produse2

Fie $A$ un sir de $N$ elemente naturale si $B$ un sir de $N - 1$ elemente cu proprietatea ca $B[~i~] = A[~i~] * A[~i+1~]$.

Avand sirul $B$, calculati cate siruri $A$ valide exista si specificati unul dintre aceste siruri.

Avand sirul $B$, reconstruiti sirul $A$.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $produse2.out$ se vor afla raspunsurile pentru cele $T$ teste. Raspunsul pentru fiecare test se va afla pe una sau doua linii: pe prima linie se va afla numarul de siruri $A$ din care rezulta sirul $B$ dat; in cazul in care exista cel putin o solutie, a doua linie va contine $N$ numere *naturale*, reprezentand unul dintre sirurile $A$ valide.

În fişierul de ieşire $produse2.out$ se vor afla raspunsurile pentru cele $T$ teste. Raspunsul pentru fiecare test are urmatorul format: in cazul in care exista solutie, va contine $N$ numere intregi, reprezentand sirul $A$; in cazul in care nu exista solutie, va contine $-1$.

h2. Restricţii

* $1 ≤ T ≤ 7000$

* $2 ≤ N ≤ 3 * 10^5^$
* $1 ≤ B[~i~] ≤ 3 * 10^6^$
* Daca exista mai multe solutii se accepta oricare dintre ele.

* Vor fi cel mult $1500000$ de numere in fisierul de intrare.

* Vor fi cel mult $10^6^$ numere in input.

h2. Exemplu

27 36 24
4
2 3 4

| 2
3 9 4 6
0

| 3 9 4 6
-1

|
== include(page="template/taskfooter" task_id="produse2") ==