bsrec

Fie un vector $v$ sortat crescător cu $N$ elemente naturale nenule distincte pe care nu le cunoaştem, dar pe care ne propunem să le determinăm. Având la dispoziţie acest vector $v$, cu ajutorul algoritmului de căutare binară prezentat în poza alăturată putem răspunde la query-uri de forma:

• Dându-se un număr $X$ şi un interval $[a, b]$ se cere să se determine cel mai mic element mai mare decât $X$ aflat în intervalul determinat de indicii $a$ şi $b$, interval din vectorul $v$.

Se cunosc paşii pe care algoritmul de căutare binară i-a urmat pentru diferite valori ale tripletului $(X, a, b)$.

Cerință

Dându-se $N$ (lungimea vectorului), $Q$ (numărul de query-uri apelate) şi cele $Q$ query-uri, să se determine vectorul iniţial. Dacă există mai multe soluţii se va afişa soluţia minim lexicografică. Dacă nu există soluţie se va afişa valoarea $-1$. Un vector $V_1$ se consideră mai mic lexicografic decât un alt vector $V_2$ dacă există un indice $i$ astfel încât: $V_1[1] = V_2[1]$, $V_1[2] = V_2[2]$, $\dots$, $V_1[i-1] = V_2[i-1]$ şi $V_1[i] < V_2[i]$.

Cele $Q$ query-uri sunt formate din:

• $X$ care reprezintă valoarea pe care o căutăm binar în vector
• $M$ care reprezintă numărul de iteraţii în algoritmul de căutare binară
• $[a, b]$ reprezentând intervalul în care se aplică algoritmul de cautare binară (perechea $(a, b)$ este considerată prima iteraţie în algoritm)
• $M-1$ perechi de indici reprezentând valorile afişate de algoritmul de căutare binară în urma fiecărei iteraţii

Date de intrare

Fişierul de intrare bsrec.in conţine pe prima linie o valoare $T$ reprezentând numărul de teste ce vor fi efectuate. Pentru fiecare din cele $T$ teste se va citi de pe prima linie valoarea $N$ (numărul de elemente ale vectorului), respectiv $Q$ (numărul de query-uri), despărţite prin câte un spaţiu.
Următoarele linii descriu cele $Q$ query-uri. În cadrul unui query, prima linie va conţine o pereche de numere $(X, M)$ despărţite printr-un spaţiu, unde $X$ reprezintă valoarea căutată în vector, iar $M$ numărul de paşi efectuaţi în căutarea binară a celei mai mici valori din vector care este mai mare decât $X$. Pe următoarea linie a query-ului se găseşte perechea de valori $(a, b)$ având semnificaţia de mai sus. Următoarele $M-1$ linii conţin perechi $(st, dr)$ de valori naturale despărţite prin câte un spaţiu care reprezintă indicii stânga, respectiv dreapta ce sunt afişaţi în urma fiecărei iteraţii a algoritmului de mai sus.

Date de ieșire

Fişierul de ieșire bsrec.out va conţine $T$ linii, linia $i$ conţinând răspunsul pentru testul $i$. Dacă testul admite soluţie, se vor afişa $N$ numere naturale nenule strict crescătoare ce vor reprezenta valorile vectorului $v$. Deoarece există mai multe soluţii, se va afişa soluţia minim lexicografică. Dacă testul NU admite soluţie, se va afişa valoarea $-1$.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq N,Q \leq 1 \ 000$
• $1 \leq X ≤ 10^9$
• $1 \leq st \leq dr \leq N$, cu excepţia ultimei perechi din căutarea binară unde $st > dr$.
• Pentru $20\%$ din punctajul total există teste cu $1 \leq N, Q \leq 10$ şi soluţia minim lexicografică admite valori până în $20$.
• Se garantează că $M \leq 15$.

Exemplu

bsrec.in

2
5 3
3 4
1 5
1 2
2 2
2 1
30 3
2 4
4 4
5 4
25 2
4 5
4 3
5 3
30 4
1 5
1 2
2 2
2 1
3 3
2 4
4 4
5 4
5 2
4 5
4 3

bsrec.out

1 3 4 25 26
-1

Explicație

Fişierul conţine $2$ teste.

Primul test are $3$ query-uri:

• Primul query caută binar valoarea $3$ în intervalul $[1, 5]$ şi face $4$ iteraţii;
• Cel de-al doilea query caută binar valoarea $30$ pe intervalul $[2, 4]$ şi face $3$ iteraţii;
• Cel de-al treilea query caută binar valoarea $25$ pe intervalul $[4, 5]$ şi face $2$ iteraţii.

Cel de al doilea test are $3$ query-uri, dar NU admite soluţie.