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

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.

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.

Exemplu

Explicaţie

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

Cum se trimit solutii?