!problema/atlas?Atlas.png!

h2. Cerinta
 
Se dă configuraţia zonei şi se cere, pentru mai multe cantităţi posibile de apă topită (exprimate în “unităţi de apă”), să se determine cea mai din dreapta poziţie pe care ajunge apa şi la ce înălţime ajunge pe acea poziţie.
 

h2. Date de intrare

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

În fişierul de intrare *atlas.in* sunt mai multe teste. Pe prima linie a fişierului se găseşte T, numărul de teste. În continuare, sunt 4∙T linii. Fiecare test este descris de 4 linii astfel: Pe prima linie a testului se găseşte n, numărul de zone pe care le poate traversa apa după ce cade (acestea sunt numerotate de la 1 la n). Se ştie că apa cade de pe zona 0 de înălţime infinită, iar la dreapta este zona n+1, de înălţime de asemenea infinită. Pe linia a doua a testului sunt n numere naturale, separate prin câte un spaţiu, reprezentând, în ordine de la 1 la n înălţimile celor n zone. Pe linia a treia a testului se găseşte q, numărul de întrebări. Pe linia a 4-a a testului sunt q numere, separate prin câte un spaţiu, ce reprezintă câte un număr de unităţi de apă care se topeşte.

h2. Date de ieşire

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

Fişierul *atlas.out* conţine câte o linie pentru fiecare întrebare a fiecărui test, în ordinea apariţiei testelor şi apoi în ordinea apariţiilor întrebărilor în fiecare test. Pe fiecare dintre acestea se află câte 2 numere separate printr-un spaţiu ce reprezintă, în ordine, răspunsul la fiecare întrebare. Primul număr este întreg şi reprezintă poziţia cea mai mare la care ajunge apa. Al doilea este un număr raţional şi reprezintă înălţimea la care ajunge apa la poziţia dată de primul număr. Acesta va fi afişat sub forma unei fracţii ireductibile “numarator/numitor”.

h2. Restricţii

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

* 1 ≤ n, q ≤ 100000
* 0 ≤ Înălţimile pilonilor ≤ 100000
* 1 ≤ Valorile din întrebări ≤ 100000 × 100000
* 1 ≤ T ≤ 3
* În scrierea numărului raţional nu se scrie spaţiu nici înainte şi nici după caracterul /

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

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

| 2
5
0 3 1 4 5
3
4 9 6
3
2 3 1
2
1 2
| 2
5
0 3 1 4 5
3
4 9 6
3
2 3 1
2
1 2

|

h3. Explicaţie
 
...

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