Fișierul intrare/ieșire:	jbird.in, jbird.out	Sursă	Concurs IQ Academy
Autor	Cristian Frâncu	Adăugată de	Cristian Francu •francu
Timp execuție pe test	0.25 sec	Limită de memorie	2300 KB
Scorul tău	N/A	Dificultate	3/5

Poți vedea testele pentru această problemă accesând atașamentele.

Vezi soluțiile trimise | Statistici

Jbird (clasa a 7-a)

J-Bird sare de pe o înălțime pe alta. Înălțimile sînt înșirate de la stînga la dreapta. J-Bird se află pe una din ele. Ea poate sări spre stînga sau spre dreapta de maxim K ori. J-Bird se întreabă cît de sus poate ajunge?

Cerință

Ajutați-o pe J-Bird să ajungă cît mai sus.

Date de intrare

Fișierul de intrare jbird.in conține pe prima linie N, numărul de înălțimi, Q, numărul de poziții de unde va pleca J-Bird și K, numărul maxim de salturi pe care îl poate face J-Bird. Pe a doua linie se vor afla cele N înălțimi, separate prin spații, așa cum se află ele înșirate, de la stînga la dreapta. Pe a treia linie se vor afla cele Q poziții ale unor înălțimi de unde va pleca J-Bird (numerotate de la unu).

Date de ieșire

În fișierul de ieșire jbird.out veți afișa Q numere. Pentru fiecare din înălțimile de plecare ale lui J-Bird veți afișa înălțimea maximă la care poate ajunge J-Bird sărind de maxim K ori către stînga sau către dreapta.

Restricții

• 1 ≤ N ≤ 200000
• 1 ≤ Q ≤ minim dintre N și 100000
• 1 ≤ K ≤ 8000
• înălțimile sînt numere întregi între 1 și 2 miliarde
• Pozițiile de unde sare J-Bird sînt numere întregi între 1 și N
• Pozițiile de unde sare J-Bird sînt unice (nu se repetă la intrare)

Exemplu