Rezolvare PBinfo #4604

Macarie a primit o nouă temă la informatică, având următorul enunț: Se consideră un șir de numere naturale nenule, A cu N elemente. Fie șirul crescător D format din toți divizorii naturali, nu neapărat distincți, ai elementelor din A. De exemplu, pentru N = 4 și A = (6,2,3,2), avem șirul D = (1,1,1,1,2,2,2,3,3,6).

Cerința

Cunoscându-se un șir Poz format din Q numere naturale nenule, reprezentând poziții din șirul D să se determine, pentru fiecare dintre acestea, elementul corespunzător din șirul D.

Date de intrare

Pe prima linie a fișierului de intrare macarie.in se află numerele naturale N și Q. Pe a doua linie se află N numere naturale nenule, reprezentând, în ordine, termenii șirului A. Pe a treia linie se află Q numere naturale nenule, reprezentând, în ordine, elementele șirului Poz. Numerele aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire macarie.out se află Q numere naturale nenule, separate prin câte un spațiu, reprezentând elemente din D, în ordinea în care pozițiile lor apar în șirul Poz.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000, 1 ≤ Q ≤ 100 000
• Numerotarea elementelor în cadrul șirurilor A, D și Poz se face începând de la 1.
• 1 ≤ Ai ≤ 1.000.000 pentru 1 ≤ i ≤ N. Termenii șirului A nu sunt neapărat distincți.
• 1 ≤ Pozi ≤ |D| pentru 1 ≤ i ≤ Q, unde |D| este lungimea șirului D.
• Datorită dimensiunilor mari, nu au fost adăugate toate testele.

Exemplul 1:

macarie.in

4 5
32 42 49 21
2 5 9 7 17

macarie.out

1 2 4 3 21

Explicație

N = 4 și Q = 5. A = (32,42,49,21) și D = (1,1,1,1,2,2,3,3,4,6,7,7,7,8,14,16,21,21,32,42,49). Pe pozițiile 2, 5, 9, 7, 17 din șir sunt valorile 1, 2, 4, 3, și 21

Exemplul 2:

macarie.in

5 4
24 56 8 490 28
35 25 28 38

macarie.out

70 12 14 490

Explicație

N = 5, Q = 4 și D[35] = 70, D[25] = 12, D[28] = 14, D[38] = 490.