Fişierul intrare/ieşire:	popa.in, popa.out	Sursă	BOI 2018
Autor	Chichirim George	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Popa

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.

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.

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.

Exemplu

.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
|

Explicaţie

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

Cum se trimit solutii?