Doodle Jump

$\text{Susi}$ s-a apucat să grindeze un joc similar cu $\text{Doodle Jump}$. În acest joc, scopul este să ghidezi un extraterestru săltăreț pe niște platforme plutitoare, încercând să ajungi cât de departe poți. Extraterestrul are un $\text{jump height } K$ fixat, iar când acesta aterizează pe o platformă la înălțimea $h$, va sări imediat, deplasându-se cu o viteză de o unitate pe secundă în sus până când ajunge la înălțimea $h+K$, apoi se deplasează cu aceeași viteză în jos, până când jucătorul îl va ghida spre o platformă.
$\text{Susi}$ este interesat de $\text{speedrun}$-ul acestui joc, așa că își pune întrebarea: "Care este timpul minim necesar (în secunde) pentru ca extraterestrul să ajungă de la prima platformă la înălțimea $y$?"

Cerință

Se dau înălțimile a $N$ platforme din jocul jucat de $\text{Susi}$ și $\text{jump height}$-ul extraterestrului. Determinați, pentru $Q$ valori $y$, care este timpul minim necesar pentru ca extraterestrul să ajungă de la prima platformă la înălțimea $y$.

Date de intrare

Pe prima linie a fișierului de intrare doodle-jump.in se găsesc trei numere întregi, $N, K, Q$, cu semnificația din enunț. Pe a doua linie se găsesc $N$ numere întregi $H_i$, sortate în ordine crescătoare, reprezentând înălțimile platformelor din joc.
Pe următoarele $Q$ linii se află câte un număr întreg $y$, reprezentând întrebările lui $\text{Susi}$.

Date de ieșire

Pe cele $Q$ linii ale fișierului de ieșire doodle-jump.out se va găsi câte un număr întreg, reprezentând răspunsul la întrebarea corespunzătoare din fișierul de intrare.

Restricții și precizări

• $1\leq N, Q\leq 100\ 000$;
• $1\leq K\leq 10^9$;
• $1\leq H_1<H_2<\dots <H_N\leq 10^{18}$;
• $H_1\leq y\leq 10^{18}$ pentru fiecare întrebare $y$;
• Se garantează că extraterestrul poate ajunge la toate platformele și la toate înălțimile din întrebări dacă el pornește de la prima platformă;
• Dacă extraterestrul aterizează pe o platformă la înălțimea $h$, acesta se va deplasa după ecuația $y(t)=h+K-\lvert t-K\rvert$ ($t$ reprezintă timpul de la începerea saltului) până când acesta aterizează pe următoarea platformă, ceea ce se poate realiza dacă $t\geq K$;
• Se consideră că extraterestrul a ajuns la înălțimea $y$ dacă acesta a atins-o la un moment dat (nu neapărat când el se află în cădere);
• În contextul problemei, extraterestrul se deplasează doar pe verticală.

Subtask-uri și punctare

Exemplul 1

doodle-jump.in

7 4 7
2 5 7 8 12 15 17
3
6
11
13
16
19
21

doodle-jump.out

1
4
13
15
18
23
29

Explicație

Pentru a doua întrebare, extraterestrul are nevoie de un salt, care pornește de pe platforma de înălțime $2$ și atinge înălțimea $6$ în vârful lui.
Pentru a treia întrebare, extraterestrul are nevoie de $3$ salturi:

• unul de la platforma de înălțime $2$ la cea de înălțime $5$ ce durează (cu tot cu coborâre) $5$ secunde;
• unul de la platforma de înălțime $5$ la cea de înălțime $8$, care durează tot $5$ secunde;
• unul de la platforma de înălțime $8$ ce atinge înălțimea $11$ în $3$ secunde.

În total el a avut nevoie de $5+5+3=13$ secunde pentru a ajunge la înălțimea $11$.