NYSE

Pe Bursa de Valori din New York, cunoscută și sub numele de NYSE – New York Stock Exchange, există un singur tip de acțiune ce se poate tranzacționa. Se cunoaște prețul zilnic al unei acțiuni de acest tip pentru o perioadă de $N$ zile consecutive: $p_i$ reprezintă prețul unei acțiuni în ziua $i \ (1 \leq i \leq N )$, exprimat în dolari.

William urmărește ce se întâmplă pe bursă, iar în fiecare zi $i$ poate tranzacționa, în total, cel mult $L_i$ acțiuni. Prin urmare, dacă în ziua $i$ vinde $S$ acțiuni (la prețul de $p_i$ dolari fiecare) și cumpără $B$ acțiuni (la prețul de $p_i$ dolari fiecare), trebuie respectate inegalitățile: $0 \leq S$, $0 \leq B$ și $0 \leq S + B \leq L_i$. De asemenea, numerele $S$ și $B$ trebuie să fie numere naturale. Atenție: nu este nevoie ca William să dețină cel puțin o acțiune pentru a putea vinde una. De exemplu, este posibil ca prima tranzacție pe care William o efectuează să fie vânzarea unei (sau a mai multor) acțiuni.

Pentru orice $i$, spunem că, la finalul zilei $i$, William și-a închis pozițiile, dacă numărul de acțiuni cumpărate în primele $i$ zile este egal cu numărul de acțiuni vândute în primele $i$ zile (incluzând și eventualele tranzacții efectuate în ziua $i$). În urma unei serii de tranzacții, profituleste egal cu diferența dintre suma totală de dolari obținută din vânzarea acțiunilor și respectiv suma totală de dolari utilizată pentru cumpărarea acțiunilor. William are nevoie să răspundă, în ordine, la $Q$ întrebări de forma: considerându-se o valoare naturală $x$, să se determine indicele minim al unei zile $j \ ($unde $1 \leq j \leq N )$, astfel încât după o serie de tranzacții în zilele $1$, $2$, . . . , $j$, profitul obținut să fie de cel puțin $x$ dolari, iar el să își fi închis pozițiile la finalul zilei $j$.
Dacă nu există niciun astfel de indice $j$, atunci se consideră că $j = −1$. William știe încă de la începutul primei zile prețurile pentru întreaga perioadă de $N$ zile, astfel că își poate planifica optim tranzacțiile, în funcție de fiecare întrebare primită.

Cerință

Scrieți un program care, cunoscând $N$ , prețul zilnic al unei acțiuni pentru cele $N$ zile, precum și limitele zilnice de tranzacționare, răspunde corect la $Q$ întrebări de forma descrisă. Cele $Q$ întrebări sunt independente între ele, în sensul că pentru fiecare întrebare se poate alege o altă serie de tranzacții din care să rezulte cea mai mică valoare a lui $j$, în cazul în care aceasta există (când $j \neq −1$).

Date de intrare

Fișierul de intrare nyse.in conține pe prima linie numărul natural $N$ . Pe următoarea linie se află $N$ numere naturale, reprezentând, în ordine: $p_1$, $p_2$, …, $p_N$. Pe următoarea linie se află $N$ numere naturale, reprezentând, în ordine: $L_1$, $L_2$, …, $L_N$ . Pe următoarea linie se află numărul natural $Q$. Pe următoarele $Q$ linii se află întrebările, câte o întrebare pe fiecare linie. O linie care reprezintă o întrebare conține un singur număr natural $x$, cu semnificația de mai sus. Numerele aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire nyse.out conține $Q$ linii. Pe cea de a $k$-a linie se află răspunsul pentru cea de a $k$-a întrebare descrisă în fișierul de intrare (unde $1 \leq k \leq Q$).

Restricții și precizări

• $1 \leq N \leq 900 \ 000$ și $1 \leq Q \leq 100 \ 000$.
• $1 \leq p_i \leq 1 \ 000 \ 000 \ 000$ și $0 \leq L_i \leq 1 \ 000$, pentru fiecare $i$: $1 \leq i \leq N$.
• $0 \leq x \leq 10^{18}$, pentru fiecare dintre cele $Q$ întrebări.
• În fiecare zi, William are și opțiunea de a nu face tranzacții.

Exemplul 1

nyse.in

2
10 5
3 3
1
14

nyse.out

2

Explicație

Se cunoaște prețul acțiunii pentru o perioadă de două zile consecutive $(N = 2)$. În prima zi, o acțiune valorează $p_1 = 10$ dolari, iar în cea de a doua zi, o acțiune valorează $p_2 = 5$ dolari. Atât în prima zi, cât și în cea de a doua, se pot tranzacționa cel mult trei acțiuni $(L_1 = L_2 = 3)$.
Avem de răspuns la o singură întrebare $(Q = 1)$, pentru care $x = 14$.
În cadrul întrebării, William alege să vândă trei acțiuni (la prețul de $10$ dolari fiecare) în prima zi și apoi să cumpere trei acțiuni (la prețul de $5$ dolari fiecare) în a doua zi. Astfel, la finalul celei de a doua zile, numărul de acțiuni cumpărate este egal cu numărul de acțiuni vândute, adică trei, deci William și-a închis pozițiile.
Profitul maxim obținut după primele două zile este egal cu: $3 \cdot 10 − 3 \cdot 5 = 15$ dolari.

Exemplul 2

nyse.in

5
10 1 20 21 25
1 1 1 1 1
1
20

nyse.out

4

Explicație

Profitul maxim care se poate obține la finalul celei de a cincea zile este de $35$ de dolari.

Exemplul 3

nyse.in

5
10 12 5 113 343
1 2 3 2 1
4
0
1000
345
21

nyse.out

1
-1
5
4

Explicație

Profitul maxim care se poate obține la finalul celei de a cincea zile este de $556$ de dolari.