C. LCM Queries
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ positive integers and $$$q$$$ queries.

On each query, you are given a positive integer $$$x$$$. You need to output $$$\max\limits_{i=1}^n \left[\mathrm{lcm}{(x, a_i)} \right]$$$.

In other words, what is the maximum least common multiple of $$$x$$$ with any number from $$$a$$$?

Input

The first line contains two integers $$$n, q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^5$$$) — the size of the array $$$a$$$, and the number of queries.

The second line contains $$$n$$$ space-separated integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — the array.

The third line contains $$$q$$$ space-separated integers $$$x_1, \ldots, x_q$$$ ($$$1 \leq x_i \leq 10^6$$$) — the queries.

Output

Output a single line containing $$$q$$$ space-separated integers — the answers to the queries.

We strongly recommend using fast I/O for this problem.

Example
Input
5 5
6 4 1 10 8
5 6 7 8 20
Output
40 30 70 40 60
Note

In the example test case, the optimal pairs are $$$\mathrm{lcm}(5, 8) = 40, \; \mathrm{lcm}(6, 10) = 30, \; \mathrm{lcm}(7, 10) = 70, \; \mathrm{lcm}(8, 10) = 40, \; \mathrm{lcm}(20, 6) = 60$$$.