Problem 1425: qvect

Se consideră $N$ vectori cu elemente întregi, numerotați de la $1$ la $N$ , sortați crescător, fiecare vector având un număr precizat de elemente.

Cerință

Să se răspundă la $Q$ întrebări de tipul:

1 i j — care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu $i$ , iar cel de al doilea element aparținând vectorului numerotat cu $j$ ?
2 i j — care este valoarea ce se găsește pe poziția mediană în vectorul obținut prin interclasarea vectorilor având numerele de ordine $i, i+1, \dots, j$ , $(i < j)$ .

Date de intrare

Fişierul de intrare qvect.in conţine pe prima linie două numerele naturale $N$ și $Q$ , separate printr-un spațiu, ce reprezintă numărul de vectori, respectiv numărul de întrebări.

Pe fiecare dintre următoarele $N$ linii se găsește descrierea unui vector sub forma: $k, a_1, a_2, \dots, a_k$ , unde $k$ reprezintă numărul de elemente, iar $a_1, \dots, a_k$ reprezintă elementele vectorului, separate prin câte un spațiu.

Pe fiecare dintre următoarele $Q$ linii se găsește descrierea unei întrebări sub forma unui triplet de numere naturale: $t, i, j$ , separate prin câte un spațiu, unde $t$ reprezintă tipul întrebării şi poate lua numai valorile $1$ sau $2$ , iar $i$ și $j$ au semnificația precizată în cerinţă.

Date de ieșire

Fişierul de ieşire qvect.out va conţine $Q$ numere întregi, câte unul pe linie, reprezentând în ordine, răspunsurile la cele $Q$ întrebări.

Restricții și precizări

$1 \leq N, i, j \leq 100$
$1 \leq Q \leq 1 \ 000$
$1 \leq t \leq 2$
$1 \leq k \leq 5 \ 000$
$-10^9 \leq a_1, a_2, \dots, a_k \leq 10^9$ .
Prin valoarea aflată pe poziția mediană a unui vector $a$ cu $k$ elemente se înțelege valoarea elementului situat pe poziţia $\lfloor \frac{k}{2} \rfloor$ , adică partea întreagă a lui $\frac{k}{2}$ .
$15\%$ dintre teste vor conține numai întrebări de tipul $1$ .
$15\%$ dintre teste vor conține numai întrebări de tipul $2$ .

Exemplul 1

qvect.in

3 3
7 1 4 5 8 11 18 19
6 2 4 5 10 21 29
4 13 14 15 15
2 2 3
1 2 3
2 1 3

qvect.out

13
3
10

Explicație

Prima întrebare este de tipul $2$ . Vectorul nou obținut prin interclasarea vectorilor numerotați cu $2$ și cu $3$ este $2, 4, 5, 10, 13, 14, 15, 15, 21, 29$ și conține $6 + 4 = 10$ elemente, valoarea elementului median este $13$ .

A doua întrebare este de tipul $1$ . Diferența minimă se obține pentru perechea $(10,13)$ , unde valoarea $10$ aparține vectorului numerotat cu $2$ , iar valoarea $13$ aparține vectorului numerotat cu $3$ .

A treia întrebare este de tipul $2$ . Poziția mediană în vectorul nou obținut prin interclasare este $\frac{7+6+4}{2} = 8$ , deci valoarea ce se găsește pe poziția mediană este $10$ .

qvect