Echilibrare

Omul este măsura tuturor lucrurilor. -- Protagoras

De trei ori am măsurat, de fiecare dată am tăiat, și tot scurtă e. -- Omul

Se consideră $2\cdot N$ urne cu bile, unde în urna $i$ sunt $A_i$ bile.
Definim o echilibrare operația ce constă în a lua orice număr de bile dintr-o singură urnă și a le muta într-o altă urnă. Mai definim de asemenea dezechilibrul total ca fiind diferența în modul dintre numărul total de bile din primele $N$ urne și numărul total de bile din ultimele $N$ urne.

Ne vom pune $Q$ întrebări de forma: pentru un $K$ dat, care este numărul minim de operații de echilibrare care fac ca dezechilibrul total să fie cel mult $K$? Întrebările sunt puse considerând conținutul urnelor de la început, adică urnele nu se modifică după o întrebare. De asemenea, pentru orice soluție posibilă definim deranjul mutării ca fiind cel mai mare număr de bile mutate într-o singură operație de echilibrare. Am vrea să aflăm și care este cel mai mic deranj care se poate obține, menținând același număr minim de operații de echilibrare.

Cerință

Pentru fiecare din cele Q întrebări, aflați numarul minim de operatii de echilibrare și deranjul minim. Pentru o întrebare se acordă punctaj parțial chiar și dacă doar primul număr este corect.

Date de intrare

Pe prima linie a fișierul de intrare echilibrare.in se află numărul $N$, iar pe a doua linie numerele $A_1$, $A_2$, $\dots$, $A_{2N}$, în această ordine, separate prin spațiu.
Pe a treia linie a fișierului de intrare se află numărul $Q$, iar pe următoarele $Q$ linii se află câte un număr $K$, corespunzător unei întrebări.

Date de iesire

Fișierul de ieșire echilibrare.out trebuie să conțină $Q$ linii, care să reprezinte răspunsurile la cele $Q$ întrebări din fișierul de intrare, în ordine. Primul număr reprezintă numărul minim de operații de echilibrare, iar al doilea număr reprezintă deranjul minim.

Restricții și precizări

• $1 \leq N \leq 250\ 000$.
• $1 \leq Q \leq 250\ 000$.
• $1 \leq A_i \leq 2\ 000\ 000$.
• Pentru orice întrebare avem $1 \leq K \leq 10^{12}$.
• Atenție! Dacă aflați numărul minim de operații corect pentru toate întrebările unui test primiți $40\%$ din punctajul testului. Pentru restul de punctaj trebuie să aflați și deranjul minim pentru toate întrebările.

Exemplul 1

echilibrare.in

1
0 10
2
1
2

echilibrare.out

1 5
1 4

Explicație

Testul conține două întrebări:

• Pentru prima avem $K=1$ și în cazul acesta ar trebui mutate 5 bile din urna a doua în prima urnă. Astfel cele două urne vor conține câte 5 bile, iar diferența în modul dintre numărul de bile din cele două jumătăți ale șirului $A$ este $0$, care este $\leq 1$.
• Pentru a doua avem $K=2$ și ar trebui mutate 4 bile din urna a doua în prima urnă. Astfel cele două urne vor conține câte 4, respectiv 6 bile, iar diferența în modul dintre numărul de bile din cele două jumătăți ale șirului $A$ este $2$, care este $\leq 2$.

Exemplul 2

echilibrare.in

3
1 1 0 5 4 5 
3
1
2
3

echilibrare.out

2 3
1 5
1 5

Explicație

Pentru prima întrebare trebuie să mutăm în total $6$ bile din două urne. Deranjul minim este $3$ pentru că putem muta câte $3$ bile din două urne.
Întrebarile rămase au același răspuns, pentru că în ambele cazuri este suficient să mutăm $5$ bile.