mediana

D. 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 ar vrea 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?

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.

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

2 3 4 5 6 7 8
0 7 0 6
3 5 1 3

2 4 3 7

2 4 3 6

5 7 1 6
| 3
3