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

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:

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.

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 ??? 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$

* 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) |_. $stdout$ |_. $stdin$ |
| 0 0 1 3 5
|
|
 
¦
| 0
|
 
| 0 4 5 1 3
|
|
 
¦
| 1
|
 
|

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
|

-1 2 -1 4 5 -1 |   | Raspuns final la problema |

h2. Explicaţie