Tarot

Cerință

În chilia întunecată a Marii Preotese Esmeralda, mirosul de smirnă și tămâie vestește începerea unui ritual străvechi. Pe masa de catifea neagră, ea a etalat un set special de $N$ cărți de Tarot distincte, numite „Arcanele de Obsidian”. Fiecare dintre aceste cărți poartă inscripționat un număr natural $V$
V, reprezentând „Greutatea Destinului”.
În această noapte, Esmeralda consideră că numărul 13 este „Numărul Destinului”, iar fiecare carte are o putere ascunsă numită Rezonanță. Matematic, Rezonanța unei cărți cu valoarea $V$ este egală cu exponentul maxim $p$ la care numărul 13 apare în descompunerea în factori primi a lui $V!$ (factorialul valorii V, adică $1 \cdot 2 \cdot \dots \cdot V$.

O carte este considerată Sacră doar dacă Rezonanța ei $p$ este un număr prim. (Exemplu: Pentru o carte cu valoarea V = 25, în produsul $1 \cdot 2 \cdot \dots \cdot 25$, numărul $13$ apare o singură dată. Rezonanța este p = 1. Deoarece 1 nu este prim, cartea nu este Sacră. Pentru o carte cu V = 26, numărul 13 apare de două ori, în factorii
13 și 26. Rezonanța este p = 2. Deoarece 2 este prim, cartea este Sacră).

Marea Preoteasă trebuie să realizeze $T$ ritualuri de divinație. Pentru fiecare ritual, ea primește o viziune sub forma unui prag numeric $V_{prag}$. Ea trebuie să găsească în setul de $N$ cărți de pe masă pe cea mai potrivită: cartea Sacră care are valoarea cea mai mică, dar care este cel puțin egală cu $V_{prag}$.

Cunoscând cele $N$ valori ale cărților etalate pe masă și cele $T$ praguri din viziuni, determinați pentru fiecare viziune valoarea cărții Sacre căutate. Dacă în setul de pe masă nu există nicio carte Sacră cu valoarea cel puțin egală cu pragul dat, afișați -1.

Date de intrare

Pe prima linie a fisierului de intrare tarot.in se află numărul natural $N$.
Pe a doua linie se află $N$ numere naturale, în ordine crescătoare, reprezentând valorile cărților.
Pe a treia linie se află numărul natural $T$.
Pe a patra linie se află cele $T$ praguri $V_{prag}$.

Date de ieșire

În fișierului de ieșire tarot.out Se vor afișa $T$ numere naturale, separate prin spațiu, reprezentând răspunsul pentru fiecare viziune.

Restricții și precizări

• $1 \le N, T \le 100 \ 000$;
• $1 \le V, V_{prag} \le 1 \ 000 \ 000$
• Cele $N$ numere reprezentând valorile cărților din fișierul de intrare sunt furnizate în ordine crescătoare.

Punctajul se acordă astfel:

• $20$ de puncte: $N, T \le 100$ și $V, V_{prag} \le 500$.
• $40$ de puncte: $N, T \le 1 \ 000$ și $V, V_{prag} \le 100 \ 000$. (Include testele pentru 20p).
• 60 de puncte: $N, T \le 10 \ 000$ și $V, V_{prag} \le 1 \ 000 \ 000$. (Include testele anterioare).
• $100$ de puncte: Restricțiile inițiale ($N, T \leq 100 \ 000$).

Exemplul 1

tarot.in

6
10 26 30 39 52 65
3
20 70 35

tarot.out

26 -1 39

Explicație

Cartea $V = 10$: Rezonanța $p = 0$, $0$ nu este număr prim → Nu este Sacră.
Cartea $V = 26$: Rezonanța $p = 2$, $2$ este număr prim → Este Sacră.
Cartea $V = 30$: Rezonanța $p = 2$, $2$ este număr prim → Este Sacră.
Cartea $V = 39$: Rezonanța $p = 3$, $3$ este număr prim → Este Sacră.
Cartea $V = 52$: Rezonanța $p = 4$, $4$ nu este număr prim → Nu este Sacră.
Cartea $V = 65$: Rezonanța $p = 5$, $5$ este număr prim → Este Sacră.

Lista valorilor sacre: $\{26, 30, 39, 65\}$

Procesarea viziunilor:

$V_{prag}$ = 20 → cea mai mica valoare sacră $\geq$ 20 este 26.
$V_{prag}$ = 70 → nu există nicio valoare sacră $\geq$ 70 → -1.
$V_{prag}$ = 35 → cea mai mica valoare sacră $\geq$ 35 este 39.