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!

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?

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
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") ==