D. Mediana

mediana

== include(page="template/taskheader" task_id="mediana") ==

Se dau doua siruri ( **A** si **B** ) sortate crescator de lungime **N** si **M**. Curios din fire, Algorel, in internship la AlgoTech, trebuie sa afle raspunsul la mai multe intrebari de forma: daca s-ar interclasa secventa [ **le1**; **ri1** ] din sirul **A** cu secventa [ **le2**; **ri2** ] din sirul **B** obtinandu-se astfel un alt sir crescator, care este elementul ce se afla pe pozitia din mijloc din sirul ce se obtine?
 
Dupa ce Algorel a rezolvat problema si a vazut cat este de interesanta, s-a decis sa o propuna la un concurs de algoritmica. Cum ONIS are loc la Cluj anul acesta, voi sunteti norocosii care trebuie sa o rezolve!
 
Dându-se **T** teste, fiecare avand doua siruri **A** si **B** cu **N** respectiv **M** elemente sortate, sa se raspunda la **Q** intrebari de forma celei explicate mai sus.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $mediana.in$ conţine pe prima linie numărul **T**, iar pe urmatoarele linii sunt descrise cele **T** teste. Fiecare test ocupa mai multe linii, in felul urmator:
 
* O linie avand valorile **N**, **M** si **Q**
* O linie avand **N** numere resprezentand sirul **A**
* O linie avand **M** numere reprezentand sirul **B**
* **Q** linii avand cate $4$ valori: **le1**, **ri1**, **le2**, **ri2**

Fişierul de intrare $mediana.in$ ...

h2. Date de ieşire

În fişierul de ieşire $mediana.out$ trebuie sa afisati mai multe linii. Pe fiecare linie se afla un singur numar, reprezentand raspunsul la cate o intrebare din fisierul de intrare. Raspunsurile trebuie sa apara in ordinea intrebarilor din fisierul de intrare.

În fişierul de ieşire $mediana.out$ ...

h2. Restricţii

* $T <= 20$
* $1 <= N, M, Q <= 100.000$
* $0 <= le1 <= ri1 < N$
* $0 <= le2 <= ri2 < M$
* Toate numerele din fisierul de intrare sunt mai mici de $2$ miliarde
* In cazul in care $L$ - lungimea sirului este para, elementul din mijloc se va considera cel de pe pozitia $L div 2$ (partea intreaga)

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. mediana.in |_. mediana.out |

| 2
5 5 8
1 2 3 4 5
1 2 3 4 5
0 0 1 4
0 1 2 4
0 2 3 4
0 3 4 4
1 4 0 0
2 4 0 1
3 4 0 2
4 4 0 3
8 7 4
1 3 6 6 7 9 13 31
2 3 4 5 6 7 8
0 7 0 6
3 5 1 3
2 4 3 6
5 7 1 6
| 3
3
3
3
3
3
3
3
6
5
6
7

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="mediana") ==