SimulareOJI9 | Macarie

Macarie has received a new problem as part of his informatics assignment, and here is its statement:

We are given an array $A$ with $N$ positive integers. Let's consider the increasing array $D$ made of all positive divisors, not necessarily distinct of the values from $A$. As an example, for $N=4$ and $A=(6, 2, 3, 2)$, we have the array $D=(1,1,1,1,2,2,2,3,3,6)$.

Task

Given an array $Poz$ made of $Q$ positive integers, representing positions from $D$, find for each of the values, the value at the respective position from the array $D$.

Input data

The first line of the input file macarie.in contains the integers $N$ and $Q$.
The second line of the input contains $N$ positive integers, representing the values from $A$.
The third line has $Q$ positive integers, representing the values from $Poz$. The numbers on the same line are separated by singular spaces.

Output data

The first line of the output file macarie.out contains $Q$ positive integers, separated by spaces, representing the values from $D$, in order in which the positions show up in $Poz$.

Constraints and clarifications

• $1\leq N \leq 1 \ 000 \ 000$, $1\leq Q \leq 100 \ 000$;
• The arrays $A$, $D$ and $Poz$ are indexed from $1$.
• $1 \leq A_i \leq 1 \ 000 \ 000$ for $1 \leq i \leq N$. The values from $A$ are not necessarily distinct.
• $1 \leq Poz_i \leq |D|$ for $1 \leq i \leq Q$, wher $|D|$ is the length of $D$.

Example 1

macarie.in

4 5 
32 42 49 21
2 5 9 7 17

macarie.out

1 2 4 3 21

Explanation

$N = 4$ and $Q = 5$. $A = (32, 42, 49, 21)$ and $D = (1, \underline{1}, 1, 1, \underline{2}, 2, \underline{3}, 3, \underline{4}, 6, 7, 7, 7, 8, 14, 16, \underline{21}, 21, 32, 42, 49)$.

Example 2

macarie.in

5 4
24 56 8 490 28
35 25 28 38

macarie.out

70 12 14 490

Explanation

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