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

Poveste şi cerinţă...

bq.  E haiduc, şi e vestit
Andrii Popa cel voinic

h2. Date de intrare

Zi şi noapte tot călare
Trage bir din drumul mare
Şi din ţară peste tot
Fug neferii cât ce pot bq.
- "Andrii Popa", Phoenix

Fişierul de intrare $popa.in$ ...

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:

h2. Date de ieşire

* 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~}$.

În fişierul de ieşire $popa.out$ ...

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. Restricţii

h2. Interacţiune

* $... ≤ ... ≤ ...$

Pentru a folosi tehnologia lui Ghiţă, afişaţi $0$ urmat de $4$ numere $a b c d$ la $stdout$, toate separate prin spaţiu alb, apoi daţi $flush$ la stdout (de exemplu cu $fflush$ in $C$ şi cu $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 separate prin spaţiu alb. Daţi $flush$ apoi la stdout.
 
h2. Restricţii şi precizări
 
* Există mereu soluţie
* Orice arbore ce respectă condiţiile va fi acceptat
* Pentru ??? puncte, $N = 100$ şi $Q = 10.000$
* Pentru ??? puncte, $N = 1.000$ şi $Q = 20.000$
* Pentru ??? 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$ |
| 0 0 1 3 5
|
|
 
¦
| 0
|
 
| 0 4 5 1 3
|
|
 
¦
| 1
|
 
|
| 1
-1 0 -1 1 -1 -1
-1 2 -1 4 5 -1
|

h3. Explicaţie

h2. Explicaţie

...

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

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