atlas

„Primăvara prin topirea zăpezii iau naștere râuri și lacuri numite Wadi, lacuri ce seacă vara.” (Wikipedia). Asta se întâmplă în Munții Atlas din nordul Africii. Noi avem de simulat aceasta în următorul mod:
Avem un șir de numere, care reprezintă înălțimile fiecărui loc în care poate ajunge apa. Fiecare element din șir reprezintă înălțimea în metri a unei zone cu lațimea de un metru. Zonele sunt lipite. Apa cade de pe poziția $0$, de la o înălțime suficient de mare și va curge spre dreapta. Numim “unitate de apă” cantitatea de apă ce ocupă o zonă a unui pătrat $1$ X $1$. De exemplu, dacă se va topi o cantitate de $4$ unități de apă, aceasta va cădea de pe zona $0$ spre dreapta și va ajunge să ocupe zonele hașurate. Se observă că dacă ajunge pe o anumită zonă apa curge spre dreapta până se lovește de un perete vertical. Noi lucrăm cu proiecția într-un plan a zonei imaginare, așa că vom considera toate elementele ca având grosime neglijabilă.

Cerință

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.

Date de intrare

Î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 \times 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.

Date de ieșire

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.

Restricții și precizări

• $1 \leq n, q \leq 100 \ 000$;
• $0 \leq$ Înălțimile pilonilor $\leq 100 \ 000$;
• $1 \leq$ Valorile din întrebări $\leq 100 \ 000 \times 100 \ 000$;
• $1 \leq T \leq 3$;
• În scrierea numărului rațional nu se scrie spațiu nici înainte și nici după caracterul /

Exemplu

atlas.in

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

atlas.out

3 2/1
4 17/4
3 10/3
1 3/1
3 2/1