Wonderland

Cerință

În Țara Minunilor O(1), Pătrățel are o grădină superbă în care se găsesc $N$ plante așezate în linie, numerotate începând cu $1$, de la stânga la dreapta. Pentru a nu se plictisi, Pătrățel s-a gândit să atribuie fiecărei plante, dintre cele $N$, un număr întreg, numit coeficient de frumusețe, care să reprezinte cât de frumoasă este o plantă în viziunea personajului nostru. Astfel, $c_i \ (1 \leq i \leq N)$ reprezintă coeficientul de frumusețe al plantei cu numărul $i$.

Într-o zi de primăvară, în Țara Minunilor O(1), vine Triunghiuleț, unul dintre cei mai buni prieteni de-ai lui Pătrățel. O ființă năstrușnică și chimist excepțional, Triunghiuleț își propune să efectueze $M$ experimente asupra celor $N$ plante din grădina lui Pătrățel. Fiecare experiment este caracterizat de o anumită valoare număr întreg $e_j \ (1 \leq j \leq M)$, cu semnificația că după ce experimentul $j$ este efectuat, coeficientul de frumusețe al fiecăreia dintre cele $N$ plante va crește cu $e_j$. Mai exact, $c_1$ devine $(c_1 + e_j)$, $c_2$ devine $(c_2 + e_j)$, $\dots$, $c_N$ devine $(c_N + e_j)$.

Timpul trece neașteptat de repede în Țara Minunilor O(1), astfel că iarna își face apariția, dar nu singură, ci împreună cu Cerculeț — bunicul lui Pătrățel. Cerculeț dorește să investigheze în detaliu grădina lui Pătrățel și într-o zi decide să îi dea $Q$ query-uri. Query-ul al $k$-lea din $Q \ (1 \leq k \leq Q)$ este caracterizat de trei numere întregi: $left_k, right_k$ și $t_k$. Se cere să se afle care este indicele minim $pos \ (0 \leq pos \leq M)$, astfel încât după efectuarea primelor $pos$ experimente (din cele $M$), fiecare plantă $i$, cu $left_k \leq i \leq right_k$, să respecte: $c_i \geq t_k$. Dacă nu există o astfel de valoare $pos$, vei răspunde cu $−1$. Atenție! $pos = 0$ (experimente) reprezintă starea inițială a grădinii, înaintea efectuării oricărui experiment.

Date de intrare

Fișierul de intrare wonderland.in conține pe prima linie numărul natural nenul $N$, reprezentând numărul de plante din grădina lui Pătrățel. A doua linie a fișierului conține $N$ numere întregi, separate între ele prin câte un spațiu, reprezentând coeficienții de frumusețe inițiali ai plantelor. Mai exact, al $i$-lea număr de pe linia a doua reprezintă coeficientul de frumusețe inițial al plantei cu indicele $i$, adică $c_i$. Pe a treia linie a fișierului se găsește numărul natural nenul $M$. A patra linie a fișierului conține $M$ numere întregi, separate între ele prin câte un spațiu, reprezentând, în ordine, valorile: $e_1, e_2, e_3, \dots, e_M$. Pe a cincea linie a fișierului se găsește numărul natural nenul $Q$. Următoarele $Q$ linii conțin, în ordine, descrierea celor $Q$ query-uri date de Cerculeț, pe cea de a $k$-a linie din $Q$ găsindu-se $left_k, right_k$, respectiv $t_k$.

Date de ieșire

Fișierul de ieșire wonderland.out conține $Q$ linii. Pe a $k$-a linie, se va afla răspunsul pentru al $k$-lea query, în ordinea în care acestea au fost date de către Cerculeț.

Restricții și precizări

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^6$
• $−10^9 \leq c_i \leq 10^9$, pentru orice $1 \leq i \leq N$
• $−10 \leq e_j \leq 100$ și $e_j \not= 0$, pentru orice $1 \leq j \leq M$
• Cele $M$ experimente sunt efectuate în ordinea: $1, 2, 3, \dots, M$.
• Coeficienții de frumusețe NU se resetează înainte de fiecare experiment! Modificările aduse de un experiment se păstrează pentru toate experimentele ce urmează.
• $1 \leq Q \leq 10^5$
• $1 \leq left_k \leq right_k \leq N$, pentru orice $1 \leq k \leq Q$
• $−10^9 \leq t_k \leq 10^9$, pentru orice $1 \leq k \leq Q$
• Experimentele concepute de Triunghiuleț sunt efectuate cu acordul lui Pătrățel.

Exemplu

wonderland.in

4
17 25 9 -2
3
4 -8 100
4
1 4 500
2 4 70
1 2 20
1 3 7

wonderland.out

-1
3
1
0

Explicație

In grădina lui Pătrățel există $4$ plante. Inițial, înainte de efectuarea oricărui experiment, coeficienții de frumusețe ai acestora sunt: $(17$, $25$, $9$, $-2)$; planta $1$ are coeficientul de frumusețe $c_1 = 17$, planta $2$ are coeficientul de frumusețe $c_2 = 25$, planta $3$ are coeficientul de frumusețe $c_3 = 9$, planta $4$ are coeficientul de frumusețe $c_4 = −2$.

Triunghiuleț efectuează $3$ experimente asupra celor $4$ plante din grădină, astfel:

• După efectuarea primului experiment, coeficienții de frumusețe vor fi: $(21, 29, 13, 2)$.
• După efectuarea primelor două experimente, coeficienții de frumusețe vor fi: $(13, 21, 5, -6)$.
• După efectuarea celor trei experimente, coeficienții de frumusețe vor fi: $(113, 121, 105, 94)$.