== include(page="template/taskheader" task_id="popa") ==

Poveste şi cerinţă...
 
h2. Date de intrare
 
Fişierul de intrare $popa.in$ ...
 
h2. Date de ieşire
 
În fişierul de ieşire $popa.out$ ...
 
h2. Restricţii
 
* $... ≤ ... ≤ ...$

bq.  E haiduc, şi e vestit
Andrii Popa cel voinic
Zi şi noapte tot călare
Trage bir din drumul mare
Şi din ţară peste tot
Fug neferii cât ce pot
- "Andrii Popa", Phoenix
 
Ghiţă are o secvenţa $S$ cu $N$ numere întregi, indexată de la 0. Cum el e regele Carpaţilor, vrea să construiască un arbore binar al căror noduri au indicii $0, 1, ..., N-1$ astfel încât:
 
* Parcurgerea inordine (adică fiu stâng, apoi rădăcină, apoi fiu drept) a arborelui este $0, 1, ..., N-1$.
* Dacă nodul $x$ este părintele nodului $y$, atunci $S{~x~}$ divide $S{~y~}$.
 
Din nefericire, haiducul vestit Andrii Popa a furat secvenţa $S$, şi Ghiţă nu mai o poate accesa direct. Cu ajutorul tehnologiei avansate (telefonul lui mobil), el poate, pentru oricare doua subsecvenţe continue $[a, b]$, $[c, d]$ ale lui $S$, să determine dacă $cmmdc(S{~a~}, ..., S{~b~}) = cmmdc(S{~c~}, ..., S{~d~})$. Din nefericire, tehnologia e scumpă - daca Ghiță o foloseşte de mai mult de $Q$ ori, va trebui să plătească mai mult. Ajutaţi-l să folosească tehnologia de cel mult $Q$ ori pentru a construi arborele dorit.
 
h2. Interacţiune
 
Problema aceasta este interactiva. Initial veti putea citi de la stdin numarul $T$ de teste care va trebui sa le rezolvati. Fiecare test va avea urmatorul format: initial veti putea citi de la $stdin$ pe $N$. Pentru a folosi tehnologia lui Ghiţă, afişaţi $0$ urmat de $4$ numere $a b c d$ la $stdout$, toate urmate (inclusiv $d$) prin spaţiu alb, apoi daţi $flush$ la stdout (de exemplu cu $fflush(stdout)$ in $C$ sau cu $std::cout << std::flush$ în $C++$). Apoi citiţi răspunsul la interogarea voastră din $stdin$ ({$1$} indică ca $cmmdc$-urile coincid, $0$ că nu).
Pentru a vă afişa răspunsul, afişaţi $1$, urmat de răspuns, în formatul următor: mai întâi rădăcina arborelui, urmată de $N$ numere, unde al $i$-lea număr reprezintă fiul stâng al lui $i-1$, sau $-1$ dacă $i+1$ nu are fiu stâng, apoi alte $N$ numere, unde al $i$-lea număr reprezintă fiul drept al lui $i-1$, sau $-1$ daca $i-1$ nu are fiu drept, toate urmate prin spaţiu alb (inclusiv ultimul numar). Daţi apoi $flush$ la stdout.
 
h2. Restricţii şi precizări
 
* Există mereu soluţie
* Orice arbore ce respectă condiţiile va fi acceptat
* Pentru $40$ puncte, $N = 100$ şi $Q = 10 000$
* Pentru $20$ puncte, $N = 1 000$ şi $Q = 20 000$
* Pentru $40$ puncte, $N = 1 000$ şi $Q = 2 000$
* $Q$ nu este vizibil programului concurentului.

h2. Exemplu

table(example). |_. popa.in |_. popa.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. stdout |_. stdin |_. Explicare |
|   | 1 6 | T si N |
| 0 0 1 3 5 |   | Interogare |
|   | 0 | Raspuns la interogare |
| 0 4 5 1 3 |   | Interogare |
|   | 1 | Raspuns la interogare |
| 1
3
-1 0 -1 1 -1 -1
-1 2 -1 4 5 -1 |   | Raspuns final la problema |

h3. Explicaţie

h2. Explicaţie

...

Aici, $S = [12, 4, 16, 2, 2, 20]$.

== include(page="template/taskfooter" task_id="popa") ==