Ciobanul Pip

Cerință

Ciobanul Pip trăiește la o stână în pustietate, alături de cele $k$ capre ale sale, numerotate de la $1$ la $k$ și fiecare având o valoare $x$ asociată. Îi place matematica la fel de mult pe cât îi plac caprele!

Muncind din greu, Pip a reușit să strângă anul acesta o sumă frumușică de bani egală cu $n$ factorial ($n!$). Deoarece e foarte mulțumit de acest succes, a hotărât, pentru a-și motiva caprele să fie la fel de harnice și anul viitor, să își recompenseze o capră cu un adăpost special pentru ea.

Pip va acorda pentru construcția acestui adăpost o sumă de bani cuprinsă în intervalul $[a,b]$, dar pentru că este un om zgârcit ar prefera să cheltuie cât mai puțin. Astfel, el va alege adăpostul al cărui cost de realizare se încadrează în bugetul său și este cel mai apropiat de marginea inferioară. Dacă toate costurile sunt mai mici decât $a$, atunci el îl va alege pe cel mai mare.

Pip a conceput un algoritm special cu scopul de a alege capra câștigătoare. Pentru că-i plac numerele prime, a decis să construiască un adăpost unei capre al cărei număr de ordine este prim. Costul unui adăpost este egal cu produsul dintre valoarea $x$ asociată caprei și numarul de ore necesare construirii sale, reprezentat de puterea indicelui caprei în descompunerea în factori primi a sumei de bani strânse de Pip anul acesta.

Ajutați-l pe ciobanul Pip să afle capra căreia îi va construi adăpost.

Date de intrare

Pe prima linie a fișierului de intrare capre.in se află numărul natural $n$.

Pe a doua linie se regăsesc numerele naturale $a$ și $b$.

Pe a treia linie se găsește numarul natural $k$.

Pe următoarea linie se află $k$ numere naturale, reprezentând valoarea asociată fiecărei capre.

Date de ieșire

Fișierul de ieșire capre.out conține un singur număr $c$, reprezentând numărul de ordine a caprei alese. Dacă există mai multe capre care respectă cerințele, se va alege capra cu numărul de ordine cel mai mic, iar dacă toate costurile sunt mai mari decât $b$ nu se va construi niciun adăpost și se va afișa $-1$.

Restricții și precizări

• $1 \le k \le 10^6$;
• $1 \le n \le 10^7$;
• $1 \le a, b \le 10^8$;
• Se garantează că $a < b$;
• $1 \le x \le 10^7$.

Exemplu

capre.in

18 
200 225 
7 
21 15 28 9 32 17 12 

capre.out

3

Explicație

Suma strânsă de Pip anul acesta este egală cu $18! = 6402373705728000$.
Descompunerea în factori primi: $18! = 2^{16}⋅3^8⋅5^3⋅7^2⋅11⋅13⋅17$
Caprele care ar putea fi alese sunt cele numerotate cu $2, 3, 5$ și $7$.

Costul adăpostului caprei $2$ este $240=16⋅15$

Costul adăpostului caprei $3$ este $224=8⋅28$

Costul adăpostului caprei $5$ este $96=3⋅32$

Costul adăpostului caprei $7$ este $24=2⋅12$

În acest caz, costul adăpostului caprei $3$ este singurul care se încadrează in bugetul lui Pip, astfel capra $3$ este cea aleasă.