Ira iubește să se joace pe telefon. Atât de mult, încât părinții au luat decizia să îi blocheze telefonul pentru a se concentra la școală. Fiind fată isteață, ea a descoperit cum poate debloca telefonul de una singură.

Pe ecranul telefonului îi apar mai multe informații:

• un număr natural N
• un șir A cu N numere naturale, numerotate de la 1 la N
• un număr natural K
• un număr natural Q, apoi Q numere x, reprezentând un indice din șirul dat.

Pentru a-și putea continua jocul ea trebuie sa răspundă corect la toate cele Q întrebări de tipul: Care este diferența între cel mai mare și cel mai mic element din secvență care începe la poziția x și are lungime k?

Cerința

Scrieți un program care citește datele și răspunde corect la toate cele Q întrebări. Ira abia așteaptă să se joace din nou pe telefon!

Date de intrare

Pe prima linie a fișierului a fișierului xk.in se află N, pe a doua linie se află cele N numere naturale, separate prin câte un spațiu, reprezentând termenii șirului A. Linia a treia conține numerele K Q, iar pe următoarele Q linii câte un număr x, cu semnificația din enunț.

Date de ieșire

Fișierul xk.out va conține Q linii. Pe linia i se va afișa răspunsul corespunzător celei de-a i-a întrebare.

Restricții și precizări

• N ≤ 1.000.000
• Elementele șirului A sunt mai mici decât 1.000.000.000
• K ≤ N
• Q ≤ 1.000.000
• x ≤ N - K + 1
• Pentru teste în valoare de 15 puncte, k=1

Exemplu:

xk.in

9
4 10 5 3 8 27 9 2 13
5 4
1
5 
2 
4

xk.out

7
25
24
25